Rozważmy graf siatkowy: wierzchołki są ustawione w siatce o $H$ wierszach i $W$ kolumnach. Oznaczmy wierzchołek w $i$-tym wierszu i $j$-tej kolumnie jako $(i, j)$.

Aby zdefiniować wagi krawędzi grafu, rozważymy cztery niemalejące ciągi $A$, $B$, $C$ oraz $D$, składające się odpowiednio z $H - 1$, $W$, $H$ oraz $W - 1$ dodatnich liczb całkowitych:

• istnieje krawędź dwukierunkowa łącząca wierzchołki $(i, j)$ oraz $(i + 1, j)$ o wadze $A_i + B_j$ dla wszystkich $i$ oraz $j$ takich, że $1 \le i \le H - 1$ oraz $1 \le j \le W$;
• istnieje krawędź dwukierunkowa łącząca wierzchołki $(i, j)$ oraz $(i, j + 1)$ o wadze $C_i + D_j$ dla wszystkich $i$ oraz $j$ takich, że $1 \le i \le H$ oraz $1 \le j \le W - 1$;
• graf nie zawiera żadnych innych krawędzi.

Znajdź całkowitą wagę krawędzi w minimalnym drzewie rozpinającym tego grafu.

Wejście

Pierwsza linia wejścia zawiera dwie dodatnie liczby całkowite $H$ oraz $W$ ($2 \le H, W \le 10^5$). Druga linia zawiera $H - 1$ liczb całkowitych $A_i$: elementy ciągu $A$. Trzecia linia zawiera $W$ liczb całkowitych $B_i$: elementy ciągu $B$. Czwarta linia zawiera $H$ liczb całkowitych $C_i$: elementy ciągu $C$. Piąta linia zawiera $W - 1$ liczb całkowitych $D_i$: elementy ciągu $D$.

Gwarantuje się, że $A_{i-1} \le A_i$, $B_{i-1} \le B_i$, $C_{i-1} \le C_i$ oraz $D_{i-1} \le D_i$ dla $i > 1$, a ponadto $1 \le A_i, B_i, C_i, D_i \le 10^6$.

Wyjście

Wypisz całkowitą wagę krawędzi w minimalnym drzewie rozpinającym danego grafu. Zauważ, że wynik może nie mieścić się w 32-bitowej liczbie całkowitej.

Przykład

Wejście 1

2 3
1
1 3 6
1 4
1 2

Wyjście 1

17

Wejście 2

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

Wyjście 2

173