[eJOI2019] 矩形染色

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

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](https://www.ejoi2019.si) Problem E. [Colouring a rectangle](https://www.ejoi2019.si/static/media/uploads/tasks/colouring-isc.pdf)。 翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)。