Balancing the Scale
Time limit1sMemory limit512 MB
Remove the fewest bricks from the tops of the towers so the total weight on the left pan equals the total on the right.
- Level
Medium6 of 10
- Topics
- Dynamic programming
- Solved
- No attempts yet
Problem
Little Bajtek received an interesting toy from his parents. It is a balance scale together with a set of weights shaped like bricks. Some of the bricks are magic and have negative weight. Bajtek used the toy to measure the weight of all sorts of objects, but that soon bored him, so he invented the following game.
The game begins with bricks arranged on the two pans of the scale so that they form some towers, each made of exactly bricks. Bajtek then tries to balance the scale in as few moves as possible. The only move he is allowed to make is removing the topmost brick from any tower.
Bajtek enjoys the game, but he cannot tell whether a chosen sequence of moves is the shortest possible. Write a program that finds the minimum number of moves needed to balance the scale, so that Bajtek can check his solutions.
Input
The first line contains three integers , , and (, ), separated by single spaces: the number of bricks in every tower, the number of towers on the left pan, and the number of towers on the right pan. Each of the next lines describes one tower on the left pan and holds integers (), separated by single spaces, giving the weights of that tower's bricks from bottom to top. The following lines describe the towers on the right pan in the same format.
Output
Print a single integer: the minimum number of moves needed to balance the scale, that is, to make the total weight on the left pan equal to the total weight on the right pan.
Hint

Explanation. The bricks on the left pan weigh in total, and those on the right weigh . To balance the pans, Bajtek can remove one brick from the top of the second tower on the left pan and one brick from the top of the first tower on the right pan; the pans then weigh , so two moves suffice.