410773: GYM104101 F Survivor

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

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

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

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

The first line of the input contains three integers $$$n, m, k$$$ $$$(1\le n\le 2\times 10^5, 1\le k, m \le 10^6)$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1\le a_i \le 10^9)$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,...,b_n$$$ $$$(1\le b_i \le 10^9)$$$.

The forth line contains $$$n$$$ integers $$$c_1,c_2,...,c_n$$$ $$$(1\le c_i \le 10^9)$$$.

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.