Considérons un graphe en grille : les sommets sont disposés en une grille de $H$ lignes par $W$ colonnes. Notons le sommet situé à la $i$-ième ligne et à la $j$-ième colonne par $(i, j)$.

Pour définir les poids des arêtes du graphe, nous considérons quatre suites non décroissantes $A$, $B$, $C$ et $D$, composées respectivement de $H - 1$, $W$, $H$ et $W - 1$ entiers positifs :

• il existe une arête bidirectionnelle reliant les sommets $(i, j)$ et $(i + 1, j)$ de poids $A_i + B_j$ pour tout $i$ et $j$ tels que $1 \le i \le H - 1$ et $1 \le j \le W$ ;
• il existe une arête bidirectionnelle reliant les sommets $(i, j)$ et $(i, j + 1)$ de poids $C_i + D_j$ pour tout $i$ et $j$ tels que $1 \le i \le H$ et $1 \le j \le W - 1$ ;
• le graphe ne contient aucune autre arête.

Trouvez le poids total des arêtes de l'arbre couvrant minimal de ce graphe.

Entrée

La première ligne de l'entrée contient deux entiers positifs $H$ et $W$ ($2 \le H, W \le 10^5$). La deuxième ligne contient $H - 1$ entiers $A_i$ : les éléments de la suite $A$. La troisième ligne contient $W$ entiers $B_i$ : les éléments de la suite $B$. La quatrième ligne contient $H$ entiers $C_i$ : les éléments de la suite $C$. La cinquième ligne contient $W - 1$ entiers $D_i$ : les éléments de la suite $D$.

Il est garanti que $A_{i-1} \le A_i$, $B_{i-1} \le B_i$, $C_{i-1} \le C_i$ et $D_{i-1} \le D_i$ pour $i > 1$, et de plus, $1 \le A_i, B_i, C_i, D_i \le 10^6$.

Sortie

Affichez le poids total des arêtes de l'arbre couvrant minimal du graphe donné. Notez que la réponse peut ne pas tenir dans un entier 32 bits.

Exemples

Entrée 1

2 3
1
1 3 6
1 4
1 2

Sortie 1

17

Entrée 2

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

Sortie 2

173