题目背景

警告：滥用本题评测将被封号

题目描述

Srečko 想给一个 $m$ 行（从 $0$ 至 $m-1$ 编号） $n$ 列（从 $0$ 至 $n-1$ 编号）的的矩形网格的每一个格子染上色。一开始，整个矩形都是白色的。每一步，他都会选择一条对角线，并给这条对角线上的所有格子染上色。每个对角线染色都需要一定的费用（忽略长度），这就导致某些对角线的染色费用有高于其他某些对角线。

你需要写一个程序，读入各个对角线的染色费用，求出将所有格子染上色的最小总费用。

注意，同一个格子被重复多次地染色是被允许的。

---

一个 $m$ 行 $n$ 列的矩形网格共有 $2n+2m-2$。

例：当 $m=4,n=3$ 时，共有 $12$ 条对角线：

输入格式

输入共 $3$ 行。

第一行：两个整数 $n,m$；

第二行：共 $m+n-1$ 个整数，描述所有 $\searrow$ 方向的对角线。第 $1$ 个整数表示 $(0,n-1)$ 这个单个的格子，第 $2$ 个整数表示 $(0,n-2),(1,n-1)$ 两个格子，以此类推。

第三行：共 $m+n-1$ 个整数，描述所有 $\nearrow$ 方向的对角线。第 $1$ 个整数表示 $(0,0)$ 这个单个的格子，第 $2$ 个整数表示 $(0,1),(1,0)$ 两个格子，以此类推。

输出格式

一个整数表示答案。

​2 2
1 3 1
1 3 1

4

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

14

提示

【输入输出样例解释】

样例 1 解释

• 在这个情况中，如下的方案可以得到最小花费：

总花费 $=1+1+1+1=4$。

样例 2 解释

• 对于这个情况，如下的方案可以使花费最小化：

总花费 $=3+2+3+3+1+2=14$。

---

【数据规模与约定】

本题采用多测试点捆绑测试，共有 7 个子任务。

• Subtask 1（10 points）：$n,m\le 4$
• Subtask 2（10 points）：$m,n\le 10$
• Subtask 3（10 points）：$m,n\le 20$
• Subtask 4（20 points）：$m,n\le 2\times 10^3$
• Subtask 5（10 points）：$m=1,n\le 2\times 10^5$
• Subtask 6（20 points）：$m=n\le 2\times 10^5$
• Subtask 7（20 points）：无其他限制。

对于所有数据，保证 $1\le m,n\le 2\times 10^5$，每条对角线的染色费用 $\in [1,10^9]$

---

【说明】

原题来自：eJOI2019 Problem E. Colouring a rectangle。

翻译提供：@_Wallace_。