New Year's '16 P6 - Cake Balancing

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

Xyene wants to bake two cakes to celebrate the new year. Unfortunately, he does not have proper equipment with which to precisely measure ingredients, but since he'll be baking two identical cakes all he needs to measure are two equal amounts of ingredients. Therefore, he's decided to use a weighing scale to measure the ingredients he'll need.

He's placed items on the left side of his scale and on the right, until he had an equal amount (by weight) on both sides. Now, Xyene wants to unload the scale, and begin baking! At any step in his unloading process, he may remove any number of items from one side of the scale. However, if the scale is ever off balance by more than grams, it will tip over, and all the expensive ingredients on it will fall off!

Xyene wants to unload the scale in such a way that it never loses balance. If he unloads optimally, how many steps will it take for Xyene to completely unload the weighing scale?

For all cases, .

Input Specification

The first line of input will contain , and .

The second line of input will contain space-separated integers representing the weight of the ingredients on the left side of the balance, with the representing the weight in grams of the ingredient.

The third line of input will contain space-separated integers representing the right side of the balance, given in the same format as the left side.

Output Specification

A single integer, the number of steps required to unload the balance. Since Xyene was able to load all the ingredients onto the scale, it is guaranteed that there must exist some way to unload the scale with it maintaining balance.

Sample Input 1

2 2 2
1 2
2 1

Sample Output 1

3

Explanation for Sample Output 1

Xyene can start from either side. Starting from the left, he removes . Next, he removes from the right side, before removing from the left side.

Sample Input 2

3 2 2
1 1 1
1 2

Sample Output 2

3

Explanation for Sample Output 2

Xyene removes off of the right side, followed by from the left side. Finally, he removes from the right side.

Sample Input 3

2 4 3
1 3
1 1 1 1

Sample Output 3

3

Sample Input 4

10 10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

Sample Output 4

7