Errores de ortografía


Submit solution

Points: 100 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type
Allowed languages
C++, Python

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 H calles en dirección este-oeste y W calles en dirección sur-norte. La forma de la ciudad es una cuadrícula de (H - 1) × (W - 1) celdas. El cruce de la i-ésima calle (1 \le i \le H) desde el norte y la j-ésima calle (1 \le j \le W) desde el oeste se denota por (i, j).

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 (1 \le i \le H) desde el norte por la unidad de longitud, tardarás A_i segundos. En otras palabras, para cada c (1 \le c \le W - 1), se tarda A_i segundos en caminar desde el cruce (i, c) hasta el cruce (i, c + 1).
  • Si se camina por la j-ésima calle (1 \le j \le W) desde el oeste por la unidad de longitud, se tardan B_j segundos. En otras palabras, por cada r (1 \le r \le H - 1), se tarda B_j segundos en caminar desde el cruce (r, j) hasta el cruce (r + 1, j).

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 (1, 1). Quieres caminar hasta el cruce (H, W). 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 (1, 1) hasta el cruce (H, W) sin dar ningún rodeo.

Entrada

Lee los siguientes datos de la entrada estándar. Los valores dados son todos enteros.

H W

A_1 A_2, ..., A_H

B_1 B_2, ..., B_W

Salida

Escribe una línea en la salida estándar. La salida debe contener el tiempo mínimo (segundos) para caminar desde el cruce (1, 1) al cruce (H, W) sin desviarse.

Restricciones

  • 2 \le H \le 100 000.
  • 2 \le W \le 100 000.
  • 1 \le A_i \le 1 000 000 000 (= 10^9) (1 \le i \le H).
  • 1 \le B_j \le 1 000 000 000 (= 10^9) (1 \le j \le W).

Subtareas

  1. (10 puntos) H \le 1 000, W \le 1 000.
  2. (30 puntos) A_i \le 1 000 (1 \le i \le H), B_j \le 1 000 (1 \le j \le W).
  3. (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 A_1 + B_2 = 1 + 5 = 6 segundos.
  • Camina de la siguiente manera: cruce (1, 1) → (2, 1) → (2, 2). Se tarda B_1 + A_2 = 2 + 3 = 5 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


  • 0
    leocar  commented on June 6, 2023, 2:10 p.m.

    Los casos de prueba ya fueron corregidos, pueden hacer un reenvio