There are players fighting the boss, and each player has its hp value. Initially, the hp value of -th player equals . There is no upper limit for the hp value of each player.

At the end of each minute, the -th person will suffer  damage; that is, the hp value of -th person will decrease . Once a player's hp value is less than or equal to , he will permanently quit the fight.

You have magical skills. You can select the -th player (if he is alive) and increase his hp value by . You can use it multiple times at any minute, but the total number of times cannot exceed .

Now you need to determine the maximum number of players that can survive after  minutes.

The first line of the input contains three integers  .

The second line contains  integers  .

The third line contains  integers  .

The forth line contains  integers  .

Print one integer ---  the number satisfying the conditions above.

3 5 2
1 1 4
1 9 1
5 1 4

2

For the first test case, at the beginning of the first minute, you can use skills on the first and third players, then they will survive.