你认为开车很容易吗？当道路结冰时，情况就完全不同了。

Nomel 市恰好有 $N + 1$ 条街道（东西走向的道路）和 $M + 1$ 条大道（南北走向的道路）。每条街道与每条大道相交，因此每条街道被分成 $M$ 个街区，每条大道被分成 $N$ 个街区。

现在是冬天，城市的每条道路都覆盖着厚厚的冰层。由于在冰上开车有些棘手，每条道路都有其通过该道路一个街区所需的特定时间。在同一条道路的所有街区中，这个时间值是恒定不变的。

显然，你只能在道路上行驶。现在你的任务是找到一条从城市西北角交叉口到东南角交叉口行驶时间最短的路线。这条路线还必须是最短的，也就是说，它必须恰好经过 $N + M$ 个街区。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 500\,000$）。

第二行包含 $N + 1$ 个正整数，按从北到南的顺序给出 Nomel 市各条街道的行驶时间。

第三行包含 $M + 1$ 个正整数，按从西到东的顺序给出 Nomel 市各大道的行驶时间。

保证这些数字均不超过 $10^9$。

输出格式

输出一个整数，表示所需的最小总行驶时间。

样例

输入样例 1

2 3
5 3 7
7 2 5 6

输出样例 1

19