Errores de ortografía
Descripción
La ciudad de IOI es un lugar de interés turístico mundial. También se la conoce como una ciudad con un entramado de calles. Usted está visitando la ciudad de IOI para hacer turismo. Tiene previsto visitar a pie un lugar famoso. Quiere llegar lo antes posible. En esta tarea, consideramos la siguiente situación simplificada.
En esta ciudad hay calles en dirección este-oeste y calles en dirección sur-norte. La forma de la ciudad es una cuadrícula de () × () celdas. El cruce de la i-ésima calle () desde el norte y la j-ésima calle () desde el oeste se denota por ().
Distintas calles pueden tener diferentes ancho, material y aglomeración. La velocidad a la que se camina puede ser diferente según la calle. Para cada calle, la velocidad se determina del siguiente modo.
- Si caminas por la i-ésima calle () desde el norte por la unidad de longitud, tardarás segundos. En otras palabras, para cada (), se tarda segundos en caminar desde el cruce () hasta el cruce ().
- Si se camina por la j-ésima calle () desde el oeste por la unidad de longitud, se tardan segundos. En otras palabras, por cada (), se tarda segundos en caminar desde el cruce () hasta el cruce ().
Para no destruir el bello paisaje de la ciudad de IOI, no está permitido caminar fuera de las calles.
Ahora te encuentras en el cruce (). Quieres caminar hasta el cruce (). Como estará cansado si camina una larga distancia, no quiere dar un rodeo. No caminará en dirección norte u oeste.
En estas condiciones, querrás llegar al destino lo antes posible.
Tarea
Escribe un programa que, dada la información de las calles, calcule el tiempo mínimo para caminar desde el cruce () hasta el cruce () sin dar ningún rodeo.
Entrada
Lee los siguientes datos de la entrada estándar. Los valores dados son todos enteros.
Salida
Escribe una línea en la salida estándar. La salida debe contener el tiempo mínimo (segundos) para caminar desde el cruce () al cruce () sin desviarse.
Restricciones
- .
- .
- () ().
- () ().
Subtareas
- (10 puntos) , .
- (30 puntos) (), ().
- (60 puntos) Sin restricciones adicionales.
Ejemplo de entrada y salida
Ejemplo de Entrada #1
2 2
1 3
2 5
Ejemplo de Salida #1
5
Hay dos formas de caminar desde el cruce (1, 1) hasta el cruce (2, 2) sin dar un rodeo.
- Camina de la siguiente manera: cruce (1, 1) → (1, 2) → (2, 2). Se tarda segundos.
- Camina de la siguiente manera: cruce (1, 1) → (2, 1) → (2, 2). Se tarda segundos.
Como el tiempo mínimo es de 5 segundos, la salida es 5. Estos dos caminos se describen en la figura siguiente. Un entero en la figura es el tiempo necesario para recorrer la unidad de longitud en la calle correspondiente.
Esta entrada de ejemplo satisface las restricciones de todas las subtareas
Ejemplo de Entrada #2
5 5
7 1 5 2 8
7 2 4 1 6
Ejemplo de Salida #2
20
Por ejemplo, si se camina desde el cruce (1, 1) hasta el cruce (5, 5) de la siguiente manera, se tardan 20 segundos. Como es imposible caminar en 19 segundos o menos, la salida es 20. Un número entero en la figura es el tiempo necesario para recorrer la unidad de longitud en la calle correspondiente.
Esta entrada de ejemplo satisface las restricciones de todas las subtareas.
Ejemplo de Entrada #3
4 6
454863204 543362989 866044086 813602010
71574269 17945210 688720933 392135202 38174709 168241720
Ejemplo de Salida #3
2737473954
Esta entrada de ejemplo satisface las restricciones de las subtareas 1, 3
Comments
Los casos de prueba ya fueron corregidos, pueden hacer un reenvio