P3891 [GDOI2014] Resource Gathering

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.

第一行三个数，$N,M,T$，表示苦工的种类、开始时拥有的资源数量以及需要达到的资源的数量。 接下来 $N$ 行，每行 2 个数 $A,B$，表示生产这种苦工所需要的资源，以及这个苦工的效率，效率即为单位时间内产生的资源的数量。

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$.

- 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