This page is still under construction.

Parts of this page are still being built. What you see may change.

Balancing the Scale

Time limit1sMemory limit512 MB

Summary
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 nn 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 nn, ll, and pp (1≤n≤501 \le n \le 50, 1≤l,p≤251 \le l, p \le 25), 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 ll lines describes one tower on the left pan and holds nn integers wk,iw_{k,i} (−50≤wk,i≤50-50 \le w_{k,i} \le 50), separated by single spaces, giving the weights of that tower's bricks from bottom to top. The following pp 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 88 in total, and those on the right weigh 99. 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 3+4+(−1)=6=7+(−2)+13 + 4 + (-1) = 6 = 7 + (-2) + 1, so two moves suffice.

Examples3

  1. Example 1

    Input
    2 2 2
    4 3
    -1 2
    7 3
    1 -2
    
    Expected output
    2
    
  2. Example 2

    Input
    1 1 1
    25
    25
    
    Expected output
    0
    
  3. Example 3

    Input
    2 1 1
    3 3
    -3 -3
    
    Expected output
    4