Ian recently bought a Nintendo Switch using the consumption voucher. He wanted to buy games from Nintendo e-shop but found that the games are way too expensive. Fortunately, the games are discounted on e-shop from time to time.
Ian sees that there are $$$N$$$ games listed on e-shop, with a price of $$$A_1, A_2, \dots, A_{N-1}, A_N$$$ dollars respectively. He has $$$D$$$ days (Day $$$1$$$ to Day $$$D$$$) to buy games with a total budget of $$$K$$$ dollars. Since Ian needs time to play the game, he would buy a maximum of $$$1$$$ game each day (can be $$$0$$$). Also, he would not buy the same game more than once.
Noted that counting from Day $$$1$$$ (today), the $$$i$$$-th game would be put to a discounted price of $$$P_i$$$ (which is obviously smaller than $$$A_i$$$) if that day is a multiple of $$$i$$$. For example, the $$$3$$$-rd game would be sold at price $$$P_i$$$ at day $$$3$$$, $$$6$$$, $$$9$$$, ... and so on.
Please help Ian to find the maximum number of games he could buy within his budget.
On the first line, there are 3 space-separated integers $$$N$$$, $$$K$$$ and $$$D$$$, the number of games listed, Ian's budget in dollars and the number of days for Ian to buy games.
On the second line, there are $$$N$$$ integers, $$$A_1, A_2, \dots, A_{N-1}, A_N$$$, the price of each game.
On the third line, there are $$$N$$$ integers, $$$P_1, P_2, \dots , P_{N-1}, P_N$$$, the discounted price of each game.
$$$1 \le N \le 10^5$$$
$$$1 \le K \le 10^9$$$
$$$1 \le D \le 5 \times 10^5$$$
$$$1 \le P_i \lt A_i \le 10^9$$$ for $$$1 \le i \le N$$$
Output the maximum of games that Ian can buy using the budget of $$$K$$$ dollars in $$$D$$$ days.
3 10 6 10 10 10 3 4 5
2
3 10000 1 2 3 4 1 1 1
1
