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