#P2430. [Poi2003]Chocolate

[Poi2003]Chocolate

题目描述

有一块 mm 行、nn 列的矩形巧克力。每次可以把当前的一个矩形沿某条网格线切成两块。每条竖线有自己的单次切割代价 xix_i,每条横线有自己的单次切割代价 yiy_i,代价与这次切开的长度无关。沿同一条线切开不同的块时,每次都要支付该线的代价。

求把整块巧克力切成 mnmn 个单位方格的最小总代价。

输入格式

第一行两个整数 n,mn,m(1≤n,m≤1041\le n,m\le10^4),分别表示列数和行数。接下来 n−1n-1 行依次给出 xix_i,再接下来 m−1m-1 行依次给出 yiy_i。所有代价均为 11 到 10001000 的整数。

输出格式

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

样例

6 4
2
1
3
1
4
4
1
2
42

波兰信息学奥林匹克组委会原题