#P2430. [Poi2003]Chocolate
[Poi2003]Chocolate
题目描述
有一块 行、 列的矩形巧克力。每次可以把当前的一个矩形沿某条网格线切成两块。每条竖线有自己的单次切割代价 ,每条横线有自己的单次切割代价 ,代价与这次切开的长度无关。沿同一条线切开不同的块时,每次都要支付该线的代价。
求把整块巧克力切成 个单位方格的最小总代价。
输入格式
第一行两个整数 (),分别表示列数和行数。接下来 行依次给出 ,再接下来 行依次给出 。所有代价均为 到 的整数。
输出格式
输出一个整数,表示最小总代价。
样例
6 4
2
1
3
1
4
4
1
2
42