Background

Description

In Warcraft III, strategic resources are collected by using Peasants, Peons, Wisps, and Acolytes.

During the development of Warcraft IV, Blizzard thought this model was too single-pattern, so they wanted to add more units to make gathering more diverse.

In the new mode, players can build more types of "workers". Different "workers" have different efficiencies, and the resources required to build different "workers" are also different.

Blizzard’s games are known for pursuing balance, so to test the balance of this new mode, they designed a method: when all races have the same starting resources, measure the time to reach a certain amount of resources. If the times are the same, the design is considered balanced.

They gave you the data and hope you can test whether the design is balanced.

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