题目描述

本题译自 eJOI2019 Problem E. Colouring a rectangle

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$ 个正整数，分别表示从上至下的这 $m + n - 1$ 个 $\searrow$ 方向的填色费用。第 $i$ 个数（对于 $i\in\{1,\ldots ,m+n-1\}$）指的是行编号与列编号之差为 $i-n$ 的对角线。因此第一个数指的是只包含单元格 $(0,n-1)$ 的对角线（第 $0$ 行，第 $n-1$ 列），第二个数指的是包含 $(0,n-2)$ 和 $(1,n-1)$ 的对角线，以此类推。这样对角线的顺序就与题目描述中图片的第一行一致。

第三行输入 $m + n - 1$ 个正整数，分别表示从上至下的这 $m + n - 1$ 个 $\nearrow$ 方向的填色费用。第 $i$ 个数（对于 $i\in\{1,\ldots ,m+n-1\}$）指的是行编号与列编号之和为 $i-1$ 的对角线。因此第一个数指的是只包含单元格 $(0,0)$ 的对角线，第二个数指的是包含 $(1,0)$ 和 $(0,1)$ 的对角线，以此类推。这样对角线的顺序就与题目描述中图片的第二行一致。

输出格式

输出将这个网格的所有单元格都涂色的最小代价。

2 2
1 3 1
1 3 1

4

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

14

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le n, m \le 2\times 10^5$，保证所有代价均在 $[1, 10^9]$ 之间。