1912: 切巧克力

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：38 解决：9

题目描述

LY想吃巧克力，但是这个巧克力特别大，我们要把一块 N×M的巧克力切成一个个 1×1 的小方块。

对于一块巧克力，我们只能从某条横线或者某条竖线（要在方格线上），而且这巧克力是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块巧克力，切割一次以后就被分割成两块，而且不能把这两块巧克力拼在一起然后一刀切成四块，只能两块分别再进行一次切割。

现在，给出从不同的线切割所要花的代价，求把整块巧克力分割成 1×1 块小方块所需要耗费的最小代价。

输入

输入文件第一行包括 lns="http://www.w3.org/1998/Math/MathML">N 和 lns="http://www.w3.org/1998/Math/MathML">M，表示长 lns="http://www.w3.org/1998/Math/MathML">N 宽 lns="http://www.w3.org/1998/Math/MathML">M 的矩阵。

第二行包括 lns="http://www.w3.org/1998/Math/MathML">N−1 个非负整数，分别表示沿着 lns="http://www.w3.org/1998/Math/MathML">N−1 条横线切割的代价。

第三行包括 lns="http://www.w3.org/1998/Math/MathML">M−1 个非负整数，分别表示沿着 lns="http://www.w3.org/1998/Math/MathML">M−1 条竖线切割的代价。

输出

输出一个整数，表示最小代价。

样例输入 复制 

2 2
3
3

样例输出 复制 

9

提示

对于 lns="http://www.w3.org/1998/Math/MathML">100% 的数据，有 lns="http://www.w3.org/1998/Math/MathML">1≤N,M≤2000。