Рассмотрим сеточный граф: вершины расположены в виде сетки из $H$ строк и $W$ столбцов. Обозначим вершину в $i$-й строке и $j$-м столбце как $(i, j)$.

Для определения весов ребер графа рассмотрим четыре неубывающие последовательности $A, B, C$ и $D$, состоящие из $H - 1, W, H$ и $W - 1$ положительных целых чисел соответственно:

• существует двунаправленное ребро, соединяющее вершины $(i, j)$ и $(i + 1, j)$, с весом $A_i + B_j$ для всех $i$ и $j$, таких что $1 \le i \le H - 1$ и $1 \le j \le W$;
• существует двунаправленное ребро, соединяющее вершины $(i, j)$ и $(i, j + 1)$, с весом $C_i + D_j$ для всех $i$ и $j$, таких что $1 \le i \le H$ и $1 \le j \le W - 1$;
• граф не содержит других ребер.

Найдите суммарный вес ребер в минимальном остовном дереве этого графа.

Входные данные

Первая строка входных данных содержит два положительных целых числа $H$ и $W$ ($2 \le H, W \le 10^5$). Вторая строка содержит $H - 1$ целых чисел $A_i$: элементы последовательности $A$. Третья строка содержит $W$ целых чисел $B_i$: элементы последовательности $B$. Четвертая строка содержит $H$ целых чисел $C_i$: элементы последовательности $C$. Пятая строка содержит $W - 1$ целых чисел $D_i$: элементы последовательности $D$.

Гарантируется, что $A_{i-1} \le A_i$, $B_{i-1} \le B_i$, $C_{i-1} \le C_i$ и $D_{i-1} \le D_i$ для $i > 1$, а также $1 \le A_i, B_i, C_i, D_i \le 10^6$.

Выходные данные

Выведите суммарный вес ребер в минимальном остовном дереве заданного графа. Обратите внимание, что ответ может не поместиться в 32-битное целое число.

Примеры

Входные данные 1

2 3
1
1 3 6
1 4
1 2

Выходные данные 1

17

Входные данные 2

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

Выходные данные 2

173