Una ciudad es una grilla de \(N \times M\) bloques. La fuente de energía, de corriente ilimitada, está conectada al bloque \((1, 1)\), y el consumo ocurre solo en el bloque \((N, M)\).

Cada bloque \((i, j)\) tiene un transformador cuya capacidad en el minuto \(t\) es \(C_{ij} + t \cdot R_{ij}\): esa es la máxima corriente que puede entrar a ese bloque. Algunos pares de bloques vecinos (que comparten un lado) están unidos por cables, que no tienen límite de corriente y funcionan en ambos sentidos. Toda la corriente que entra a un bloque debe salir de él, salvo en \((N, M)\), que la consume.

La capacidad de la red en el minuto \(t\) es el máximo flujo de corriente desde la fuente hasta el bloque \((N, M)\). Calcula la mayor capacidad de la red entre todos los minutos enteros \(t \in [0, K]\).

Entrada

La primera línea tiene cuatro enteros \(N\), \(M\), \(P\) y \(K\) \((2 \le N, M \le 300,\ P \ge 0,\ 0 \le K \le 10^{12})\): las dimensiones, la cantidad de cables y el último minuto posible.

Siguen \(N\) líneas con \(M\) enteros cada una: los \(C_{ij}\) \((0 \le C_{ij} \le 10^{12})\).

Siguen \(N\) líneas con \(M\) enteros cada una: los \(R_{ij}\) \((-10^6 \le R_{ij} \le 10^6)\).

Cada una de las últimas \(P\) líneas describe un cable con cuatro enteros \(X_1\), \(Y_1\), \(X_2\), \(Y_2\) \((1 \le X_1, X_2 \le N,\ 1 \le Y_1, Y_2 \le M)\), que une los bloques \((X_1, Y_1)\) y \((X_2, Y_2)\).

Se garantiza que \(C_{ij} + t \cdot R_{ij} \ge 0\) para todo bloque y todo \(t \in [0, K]\), que cada cable une dos bloques vecinos y que no hay cables repetidos.

Salida

Una línea con un entero: la mayor capacidad de la red en un minuto entero de \([0, K]\).

Ejemplo 1

Entrada

2 2 3 10
5 4
5 6
0 0
0 0
2 1 1 1
1 1 1 2
1 2 2 2

Salida

4

Ejemplo 2

Entrada

2 3 6 12
25 1 18
10 2 50
0 2 -1
1 0 -2
1 1 1 2
1 2 1 3
1 3 2 3
1 1 2 1
2 1 2 2
2 2 2 3

Salida

14

Ejemplo 3

Entrada

2 2 1 1000000000000
5 4
5 6
0 0
0 0
2 1 1 1

Salida

0

Regional Latinoamericana 2025 del ICPC, problema G («Gridoland Power Gauge»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.