[Poi2003]Chocolate
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
有一块的矩形巧克力，准备将它切成块。巧克力上共有条横线和条竖线，你每次可以选择一块，沿着上面的一条横线或竖线将巧克力切开，无论切割的长短，沿着每条横线切一次的代价依次为，而沿竖线切割的代价依次为，，…，。 求将这块巧克力切成块的最小代价和。
Format
Input
第一行为两个整数。 接下来行，每行一个整数，分别代表，，…，。 接下来行，每行一个整数，分别代表，，…，。
Output
输出一整数，为切割巧克力的最小代价。
Samples
6 4
2
1
3
1
4
4
1
2
42
Limitation
%的数据，； %的数据，。