Srečko 想要给一个有 $m$ 行（编号从 $0$ 到 $m-1$）和 $n$ 列（编号从 $0$ 到 $n-1$）的矩形网格涂色。最初，网格中的所有单元格都是白色的。在每一步中，他选择一条对角线，并用他最喜欢的颜色涂满该对角线上的所有单元格。然而，无论对角线的长度如何，某些对角线的涂色成本可能比其他对角线更高。给定每条对角线的涂色成本，请编写一个程序来告诉 Srečko 涂满网格中所有单元格的最小总成本。注意，单元格可以被涂色多次。

一个有 $m$ 行和 $n$ 列的矩形网格共有 $2m + 2n - 2$ 条对角线。例如，如果 $m = 4$ 且 $n = 3$，则共有 12 条对角线：

输入格式

输入包含三行。

第一行包含数字 $m$ 和 $n$。

第二行包含 $m + n - 1$ 个数字，指定了沿 $\searrow$ 方向的对角线的涂色成本。第 $i$ 个数字（对于 $i \in \{1, \dots, m + n - 1\}$）指的是行索引与列索引之差为 $i - n$ 的对角线。因此，第一个数字指的是仅包含单元格 $(0, n-1)$ 的对角线，第二个数字指的是包含单元格 $(0, n-2)$ 和 $(1, n-1)$ 的对角线，依此类推。对角线的顺序与上图中第一行的顺序相同。

第三行包含 $m + n - 1$ 个数字，指定了沿 $\nearrow$ 方向的对角线的涂色成本。第 $i$ 个数字（对于 $i \in \{1, \dots, m + n - 1\}$）指的是行索引与列索引之和为 $i - 1$ 的对角线。因此，第一个数字指的是仅包含单元格 $(0, 0)$ 的对角线，第二个数字指的是包含单元格 $(1, 0)$ 和 $(0, 1)$ 的对角线，依此类推。对角线的顺序与上图中第二行的顺序相同。

输出格式

输出涂满网格的最小成本。

数据范围

• $1 \le m \le 2 \cdot 10^5$。
• $1 \le n \le 2 \cdot 10^5$。
• 成本是区间 $[1, 10^9]$ 内的整数。

子任务

• 10 分：$m, n \le 4$。
• 10 分：$m, n \le 10$。
• 10 分：$m, n \le 20$。
• 20 分：$m, n \le 2000$。
• 10 分：$m = 1$ 且 $n \le 2 \cdot 10^5$。
• 20 分：$m = n \le 2 \cdot 10^5$。
• 20 分：无附加限制。

样例

样例输入 1

2 2
1 3 1
1 3 1

样例输出 1

4

说明 1

在这种情况下，必须涂色以下对角线以使总成本最小：

所选的每条对角线成本均为 1，因此总成本为 4。

样例输入 2

4 3
2 3 9 3 4 3
2 3 3 1 2 4

样例输出 2

14

说明 2

这一次，以下对角线以最小总成本覆盖了网格：

所选对角线的涂色成本分别为 3, 2, 3, 3, 1 和 2（按此顺序）。