问题 M: 切割

问题 M: 切割

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

题目描述

暑假无聊，小明有块 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

[提交][状态]