Descripción

Las tres pistas coincidían. La maniobra del altímetro apuntaba al suroeste de la sierra; el libro de la casa de empeño daba la fecha; las cajas del aserradero daban el tamaño del bulto. Todo llevaba al mismo lugar: los socavones abandonados de Santa Bárbara.

Renata Quijada bajó con una lámpara, un plano viejo y un problema. La mina se puede ver como una cuadrícula de ~R~ filas por ~C~ columnas donde cada celda trae un número:

• Un ~0~ significa roca: por ahí no se pasa.
• Un número ~g_{ij} \ge 1~ significa túnel, y ese número es el nivel de gas acumulado en esa celda.

Renata se mueve entre celdas de túnel ortogonalmente vecinas (arriba, abajo, izquierda o derecha); no puede caminar en diagonal ni atravesar la roca. Cada movimiento a una celda vecina cuenta como un paso.

Antes de bajar hay que graduar la mascarilla en un nivel entero ~X~. Con la mascarilla en ~X~, Renata puede pisar únicamente las celdas de túnel cuyo nivel de gas sea menor o igual que ~X~ — eso incluye la bocamina por la que entra y la propia cámara a la que quiere llegar. Una mascarilla más alta protege más, pero es más cara y más pesada, así que a Renata le interesa el ~X~ más chico que le sirva.

Hay un segundo problema: el tanque de oxígeno le alcanza para a lo más ~K~ pasos en total.

La mina tiene ~E~ bocaminas y Renata puede empezar por la que ella quiera. En algún punto está la cámara donde se escondió el fragmento del meteorito.

Escribe un programa que determine el menor nivel ~X~ con el que Renata puede llegar de alguna bocamina a la cámara dando a lo más ~K~ pasos.

Entrada

La primera línea contiene tres enteros ~R~, ~C~ y ~K~: las filas, las columnas y la cantidad máxima de pasos.

Las siguientes ~R~ líneas contienen ~C~ enteros cada una: el renglón ~i~ describe los valores ~g_{i1}, g_{i2}, \ldots, g_{iC}~.

La siguiente línea contiene un entero ~E~: la cantidad de bocaminas.

Cada una de las siguientes ~E~ líneas contiene dos enteros ~r~ y ~c~: las coordenadas de una bocamina. Las filas se numeran desde ~1~ y las columnas también.

La última línea contiene dos enteros ~f~ y ~h~: las coordenadas de la cámara del meteorito.

Se garantiza que toda bocamina y la cámara son celdas de túnel (su valor no es ~0~). Puede haber bocaminas repetidas.

Salida

Una sola línea con un entero: el menor nivel ~X~ al que se puede graduar la mascarilla[cite: 4]. Si no hay ningún nivel con el que Renata alcance la cámara en ~K~ pasos o menos, imprime -1.

Ejemplos

Ejemplo 1

Entrada

3 5 10

1 1 1 1 1

9 9 9 9 1

1 1 1 1 1

1

1 1

3 1

Salida

1

Explicación La bocamina está en la esquina superior izquierda y la cámara en la esquina inferior izquierda. Cruzar directo hacia abajo son sólo ~2~ pasos, pero obliga a pisar una celda con gas ~9~.

Con ~10~ pasos de oxígeno le alcanza para rodear por la derecha: baja por la columna ~5~ y regresa por el renglón ~3~, pisando puras celdas de gas ~1~. Son exactamente ~10~ pasos, así que la mascarilla más barata que sirve es la de nivel ~1~.

Ejemplo 2

Entrada

3 5 2

1 1 1 1 1

9 9 9 9 1

1 1 1 1 1

1

1 1

3 1

Salida

9

Explicación La misma mina, pero ahora el oxígeno sólo alcanza para ~2~ pasos. El rodeo barato ya no cabe: la única ruta de ~2~ pasos cruza la celda de gas ~9~, así que hay que graduar la mascarilla en ~9~.

Ejemplo 3

Entrada

3 5 1

1 1 1 1 1

9 9 9 9 1

1 1 1 1 1

1

1 1

3 1

Salida

-1

Explicación Con un solo paso de oxígeno no se llega a la cámara por ninguna ruta, sin importar qué tan potente sea la mascarilla.

Límites

• ~1 \le R, C \le 1\,000~
• ~0 \le K \le 1\,000\,000\,000~
• ~0 \le g_{ij} \le 1\,000\,000~
• ~1 \le E \le R \cdot C~
• ~1 \le r, f \le R~ y ~1 \le c, h \le C~

La entrada llega a tener un millón de números: conviene leerla con scanf, o con cin después de ios_base::sync_with_stdio(false).

Subtareas

Grupo	Puntos	Restricciones adicionales
1	15	~R, C \le 30~
2	20	~K \ge R \cdot C~ (el oxígeno nunca es la restricción)
3	25	Todo nivel de gas vale ~1~ o ~2~
4	40	Sin restricciones adicionales