Considera un grafo de cuadrícula: los vértices están alineados en una cuadrícula de $H$ filas por $W$ columnas. Denotemos al vértice en la fila $i$-ésima y columna $j$-ésima como $(i, j)$.

Para definir los pesos de las aristas del grafo, consideraremos cuatro secuencias no decrecientes, $A$, $B$, $C$ y $D$, que consisten en $H - 1$, $W$, $H$ y $W - 1$ enteros positivos, respectivamente:

• existe una arista bidireccional que conecta los vértices $(i, j)$ y $(i + 1, j)$ con peso $A_i + B_j$ para todo $i$ y $j$ tal que $1 \le i \le H - 1$ y $1 \le j \le W$;
• existe una arista bidireccional que conecta los vértices $(i, j)$ y $(i, j + 1)$ con peso $C_i + D_j$ para todo $i$ y $j$ tal que $1 \le i \le H$ y $1 \le j \le W - 1$;
• el grafo no contiene otras aristas.

Encuentra el peso total de las aristas en el árbol de expansión mínima de este grafo.

Entrada

La primera línea de la entrada contiene dos enteros positivos $H$ y $W$ ($2 \le H, W \le 10^5$). La segunda línea contiene $H - 1$ enteros $A_i$: los elementos de la secuencia $A$. La tercera línea contiene $W$ enteros $B_i$: los elementos de la secuencia $B$. La cuarta línea contiene $H$ enteros $C_i$: los elementos de la secuencia $C$. La quinta línea contiene $W - 1$ enteros $D_i$: los elementos de la secuencia $D$.

Se garantiza que $A_{i-1} \le A_i$, $B_{i-1} \le B_i$, $C_{i-1} \le C_i$ y $D_{i-1} \le D_i$ para $i > 1$, y además, $1 \le A_i, B_i, C_i, D_i \le 10^6$.

Salida

Imprime el peso total de las aristas en el árbol de expansión mínima del grafo dado. Ten en cuenta que la respuesta puede no caber en un entero de 32 bits.

Ejemplos

Entrada 1

2 3
1
1 3 6
1 4
1 2

Salida 1

17

Entrada 2

4 3
1 13 15
3 6 11
3 6 6 11
9 17

Salida 2

173