Description

There are $n$ trees. Initially, the $i$-th tree has height $H_i$, and every month the $i$-th tree grows by $A_i$. There is an order for a total timber length of $S$. The client requires each piece of timber to have length at least $L$, and each piece must be a whole tree (i.e., you cannot take only part of a tree). What is the minimum number of months you need to wait to fulfill the order?

Input Format

The first line contains $3$ non-negative integers $n$, $S$, $L$ separated by spaces, denoting the number of trees, the total required length, and the minimum length for a single piece, respectively.

The second line contains $n$ non-negative integers $H_1, H_2, \ldots, H_n$.

The third line contains $n$ non-negative integers $A_1, A_2, \ldots, A_n$.

Output Format

Output a single integer on one line representing the answer.

3 74 51
2 5 2
2 7 9

7

Hint

For the sample, after six months, the heights of the trees are $14$, $47$, $56$, and the order cannot be fulfilled.

After seven months, the heights are $16$, $54$, $65$. You can then cut down the $2$-nd and $3$-rd trees to fulfill the order.

From CodePlus 2017 November Contest, proudly presented by the Student Association for Algorithms and Competitions, Department of Computer Science and Technology, Tsinghua University.

Credit: idea/Zheng Linkai, problem setter/Zheng Linkai, tester/Wang Yuzhong.

Git Repo: https://git.thusaac.org/publish/CodePlus201711

Thanks to Tencent for supporting this contest.

Translated by ChatGPT 5