P10387 [Lanqiao Cup 2024 NOI Qualifier A] Training Soldiers

In the Lanqiao Kingdom, there are $n$ soldiers. These soldiers need to take a series of special trainings to improve their combat skills. For the $i$-th soldier, the cost of one training is $p_i$ gold coins, and to become a top warrior, he needs at least $c_i$ trainings. To make training more efficient, the kingdom provides a "group training" plan. This plan includes one required training for each soldier, and the total cost is only $S$ gold coins (the group training plan can be purchased multiple times, which means soldiers can take group training multiple times). As the training commander, please compute the minimum number of gold coins needed to make all soldiers become top warriors.

The first line contains two integers $n$ and $S$, separated by a space, representing the number of soldiers and the cost of one group training. The next $n$ lines each contain two integers $p_i$ and $c_i$, separated by a space, representing the cost of one training for the $i$-th soldier and the number of trainings required to become a top warrior.

Output one line containing one integer, representing the minimum number of gold coins needed to make all soldiers become top warriors.

The training method with the minimum cost is: do group training $2$ times, costing $2 \times 6 = 12$ gold coins. At this point, soldiers $1$ and $3$ have become top warriors. Then spend another $4$ gold coins to let soldier $2$ do two more trainings and become a top warrior. The total cost is $12 + 4 = 16$. For $40\%$ of the testdata, $1 \le n \le 10^3$, $1 \le p_i, c_i \le 10^5$, $1 \le S \le 10^7$. For all testdata, $1 \le n \le 10^5$, $1 \le p_i, c_i \le 10^6$, $1 \le S \le 10^{10}$. Translated by ChatGPT 5