P3891 [GDOI2014] Resource Gathering

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

魔兽争霸 3 中，战略资源的采集通过使用农民、苦工、小精灵以及寺僧来进行。 在魔兽争霸 4 的开发中，玻璃渣觉得这种模式太过单一，于是他们想添加更多的单位来使采集的模式更加丰富。 在新的模式中，玩家可以建造更多种类的“苦工”，不同的“苦工”的工作效率不同，同时，建造不同的“苦工”所需要的资源也是不一样的。 玻璃渣出品的游戏以追求平衡著称，所以为了测试这种新的模式的平衡性，他们设计了一套检测的方法：在各种族的起始资源相同时，测量达到某一资源数量的时间，如果相同则可以认为设计是平衡的。 他们将数据给你，希望你能测试出设计是否平衡。

第一行三个数，$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