京都是一座世界闻名的观光城市，也以其棋盘式的街道布局而闻名。你现在正在京都观光，计划步行前往一个著名景点。你希望尽可能早地到达那里。在本题中，我们考虑以下简化的情况。

在这座城市中，有 $H$ 条东西向的街道和 $W$ 条南北向的街道。城市的形状是一个 $(H - 1) \times (W - 1)$ 的网格。从北向南数的第 $i$ 条街道（$1 \le i \le H$）与从西向东数的第 $j$ 条街道（$1 \le j \le W$）的交叉点记为 $(i, j)$。

不同的街道可能有不同的宽度、材质和拥挤程度。你在不同街道上的步行速度可能不同。对于每条街道，你的步行速度确定如下：

• 如果你在从北向南数的第 $i$ 条街道（$1 \le i \le H$）上行走单位长度，需要 $A_i$ 秒。换句话说，对于每个 $c$（$1 \le c \le W - 1$），从交叉点 $(i, c)$ 走到交叉点 $(i, c + 1)$ 需要 $A_i$ 秒。
• 如果你在从西向东数的第 $j$ 条街道（$1 \le j \le W$）上行走单位长度，需要 $B_j$ 秒。换句话说，对于每个 $r$（$1 \le r \le H - 1$），从交叉点 $(r, j)$ 走到交叉点 $(r + 1, j)$ 需要 $B_j$ 秒。

为了不破坏京都美丽的景观，你不能在街道之外行走。现在你位于交叉点 $(1, 1)$，想要走到交叉点 $(H, W)$。由于长距离行走会感到疲劳，你不想绕路。你不会向北或向西行走。在此条件下，你希望尽可能早地到达目的地。

编写一个程序，在给定街道信息的情况下，计算从交叉点 $(1, 1)$ 到交叉点 $(H, W)$ 且不绕路的最短步行时间。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$H \ W$ $A_1 \ A_2 \ \dots \ A_H$ $B_1 \ B_2 \ \dots \ B_W$

输出格式

输出一行到标准输出。输出应包含从交叉点 $(1, 1)$ 到交叉点 $(H, W)$ 且不绕路的最短步行时间（秒）。

数据范围

• $2 \le H \le 100\,000$
• $2 \le W \le 100\,000$
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le H$)
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le W$)

子任务

1. (10 分) $H \le 1\,000, W \le 1\,000$
2. (30 分) $A_i \le 1\,000$ ($1 \le i \le H$), $B_j \le 1\,000$ ($1 \le j \le W$)
3. (60 分) 无附加限制

样例

输入格式 1

2 2
1 3
2 5

输出格式 1

5

说明

从交叉点 $(1, 1)$ 到交叉点 $(2, 2)$ 且不绕路有两种走法：

• 按以下方式行走：交叉点 $(1, 1) \to (1, 2) \to (2, 2)$。耗时 $A_1 + B_2 = 1 + 5 = 6$ 秒。
• 按以下方式行走：交叉点 $(1, 1) \to (2, 1) \to (2, 2)$。耗时 $B_1 + A_2 = 2 + 3 = 5$ 秒。

由于最短时间为 5 秒，输出 5。这两种走法如下图所示。图中的整数表示在相应街道上行走单位长度所需的时间。

输入格式 2

5 5
7 1 5 2 8
7 2 4 1 6

输出格式 2

20

说明

例如，如果你按以下方式从交叉点 $(1, 1)$ 走到交叉点 $(5, 5)$，耗时 20 秒。由于不可能在 19 秒或更短时间内到达，输出 20。图中的整数表示在相应街道上行走单位长度所需的时间。

输入格式 3

4 6
454863204 543362989 866044086 813602010
71574269 17945210 688720933 392135202 38174709 168241720

输出格式 3

2737473954