问题 D: 不爱劳动的瑞瑞

问题 D: 不爱劳动的瑞瑞

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 8
[提交] [状态] [讨论版] [命题人:]

题目描述

瑞瑞是个特别懒惰的小朋友,上信息课的时候经常有奇奇怪怪的想法。

瑞瑞的的包里有块 n*m 的长方形木板,瑞瑞想把木板全部切成 1*1 的小正方

形(用来制作拼图)。但木板本身并不均匀,因此从不同的线切割下去要花不同的

代价。而且对于一块木板,切割一次以后就被分割成两块,而且由于不能把这两

块木板拼在一起然后一刀切成四块(动静太大),所以只能两块分别再进行一次

切割。现在瑞瑞 并不想花太多的力气,所以他来找你帮他求一求最小的代价。


输入

第一行包括 N 和 M(1 ≤ N,M ≤ 1000),表示长 N 宽 M 的矩阵。
第二行包括 N-1 个非负整数,分别表示沿着 N-1 条横线切割的代价。
第三行包括 M-1 个非负整数,分别表示沿着 M-1 条竖线切割的代价。

输出

输出一行一个整数,表示最小切割代价。

样例输入

2 2
3
3

样例输出

9

提示

对于 60% 的数据:n ≤ 100;
对于 100% 的数据:n ≤ 1000,切割代价<=1000。

[提交][状态]