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
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 to completely unload the weighing scale?
Constraints
For all cases,
Subtask 1 [20%]
Subtask 2 [80%]
Input Specification
The first line of input will contain
The second line of input will contain
The third line of input will contain
Output Specification
A single integer, the number of steps required to unload the balance. Since
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
Sample Input 2
3 2 2
1 1 1
1 2
Sample Output 2
3
Explanation for Sample Output 2
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
Comments
Explanation of the forth sample please? i see it should be 8 not 7
first take 10 from left, 10 1 9 from right, 1 9 2 8 from left, 2 8 3 7 from right, 3 7 4 6 from left, 4 5 6 from right, 5 from left.