1329 . DarkShik's Chocolate
Description
DarkShik (A. K. A 黑暗陳庭緯) just made one big piece of chocolate on Valentine's day, and he wants to cut it into smaller pieces for distribution. The chocolate can be described as a n x m square. His target is to make some cuts and finally get nm pieces of 1 x 1 chocolate.
Of course, the cuts must be done at integral points. In addition, he can only cut one piece at one time. It means that he can't put two pieces side by side and cut them into four pieces in one operation. <p>
When he started cutting, he realized cutting at different positions costs him different efforts. As the picture below, if he makes all horizontal cuts first, then it costs him y1 + y2 + y3 to get four 1 x 6 pieces. The remaining cuts will cost 4(x1 + x2 + x3 + x4 + x5). <p>
Given the size of the chocolate, and the costs to cut at different positions, write a program that calculates the minimum cost to cut it into 1 x 1 pieces.
Input Format
Each test case starts with two integers, N, M (1 <= N, M <= 200,000), denoting the length and width of the chocolate. Following are N – 1 integers each on a line, which give the cost for vertical cuts, then M – 1 integers each on a line, which give the cost for horizontal cuts.
The range of costs is [-100, 100].
Output Format
An integer, which is the minimum cost of cutting.
Sample Input 1
3 2 4 2 3 6 4 2 1 3 1 4 4 1 2
Sample Output 1
14 42
Hints
Problem Source
Migrated from old NTUJ.
朱柏澂 TOI 2011
Subtasks
| No. | Testdata Range | Score |
|---|