Output Format

Print a single number: the minimum time when the amount of resources reaches $T$.

Note: Unlike in Warcraft III, in Warcraft IV producing workers takes no time. Also, resource collection is not continuous. That is, if a worker’s efficiency is $2$, they will harvest $2$ resources at time $1$, and will not harvest $1$ resource at time $0.5$.

1 1 8
1 1

4

2 1 8
1 1
2 8

3

Hint

• For $30\%$ of the testdata, $N \le 10$, $M, T \le 300$.
• For $100\%$ of the testdata, $N \le 100$, $M, T \le 1000$, $A, B \le 2^{31}$.
• The testdata guarantees that a solution exists.

Translated by ChatGPT 5