Problem Description
Jack was addicted to a fighting game recently. The game is similar to a famous anime “Fate Stay Night”. In the game, you should control your “servant” Saber to fight another “servant” Berserker.
Berserker is a famous hero who has a lot of lives. In every life, he has some “blood points”. For example, he may have 100 blood points in his first life and 200 blood points in his second life. When Berserker loss all blood points in a life, he is killed. But he will become alive immediately with next life. When there is no next life left, Berserker is really dead and you win.
Saber can attack Berserker for N times. During each attack, Saber releases a fire bird to fight Berserker. Each fire bird has some “power points”.
A fire bird can make Berserker loss blood points. But if Berserker loss one blood point, the fire bird also will loss one power point. When the power points of a fire bird become zero, the fire bird dies.
A living fire bird may be in two statuses:“young”or “old”.
When a fire bird is just released, it is “young”. After it kills Berserker once or more, it becomes“old”.
Let’s suppose a fire bird with remaining n power points fighting Berserker with remaining m blood points in his current life:
If n> m: Berserker will be killed and becomes alive immediately with his next life(if he has), and then the fire bird will be“old”and fight Berserker again with remaining n-m power points.
If n = m: Berserker will be killed and becomes alive with his next life (if he has), and the fire bird dies.
If n < m: In this situation, if the fire bird is “young”, it will die after making Berserker loss n blood points. But if the fire bird is “old”, it just dies without doing any harm to Berserker.
As the “Master” of Saber, you can use “Command Mantra” M times. You can use “Command Mantra”to double a fire bird’s power points, but you can’t use “Command Mantra”more than once on a same fire bird. Now there is the question: How many times can you kill Berserker at most?
Input
There are several data cases, ended with “0 0 0”
For each test case:
The first line contains three integers N,M,K, meaning the number of attacks of Saber, the times of Command Mantra you can use and the number of lives of Berserker.
The second line contains N integers, indicating the power points of N fire birds, in the order of attacking. You can’t change the attacking order.
The third line contains K integers, meaning the blood points of all Berserker’s lives. The first integer is for his first life, the second integer is for his second life, etc.
Please note: 1<=N<=10000, 0<=M<=100, 0<=K<=100000. All power points and blood points are no more than 10000 and none negative.
Output
For each test case, output one line containing the maximum times that you can kill Berserker.
Sample Input
10 0 20
8 9 8 7 5 7 5 5 0 2
3 0 2 1 7 1 5 5 7 0 6 1 5 6 7 3 1 0 5 8
10 1 0
6 0 0 7 7 7 1 7 6 7
0 0 0
Sample Output
12
0
