P16695 [CSPro 29] Land Reclamation Plan

Luogu’s testdata is for community communication only and is not official testdata. Official judging link: .

Dundun selected a total of $n$ regions to reclaim into farmland. Since the regions have different sizes, the time needed to reclaim them is also different. It is estimated that the reclamation time of region $i$ ($1 \le i \le n$) is $t_i$ days. These $n$ regions can be reclaimed at the same time, so the total time $t_{Total}$ depends on the region that takes the longest time, namely: $$ \begin{aligned} t_{Total} = \max\{t_1, t_2, \cdots, t_n\} \end{aligned} $$ To speed up the progress, Dundun plans to invest extra resources in some regions to reduce the reclamation time. Specifically: - For region $i$, every time you invest $c_i$ units of resources, you can reduce its reclamation time by $1$ day. - The number of days reduced must be an integer, meaning the amount of resources invested in region $i$ must be an integer multiple of $c_i$. - For region $i$, you can invest at most $c_i \times (t_i - k)$ units of resources to reduce its reclamation time to $k$ days. - Here, $k$ is the minimum number of days to reclaim one region, satisfying $0 < k \le \min\{t_1, t_2, \cdots, t_n\}$. In other words, if resources were unlimited, all regions could be reclaimed in $k$ days. Now Dundun has a total of $m$ units of resources available. Compute the minimum number of days needed to reclaim all $n$ regions.

Read input from standard input. There are $n + 1$ lines in total. The first line contains three positive integers $n$, $m$, and $k$ separated by spaces, representing the total number of regions to be reclaimed, the amount of resources Dundun has, and the minimum reclamation days for each region. The next $n$ lines each contain two positive integers $t_i$ and $c_i$ separated by spaces, representing the reclamation time of region $i$ and the amount of resources needed to reduce the time by $1$ day.

Write output to standard output. Output one integer, representing the minimum total time to reclaim the $n$ regions.

### Explanation for Sample 1 As shown in the table below, investing $5$ units of resources can reduce the total time to $5$ days. At this point, Dundun still has $4$ units of resources left, but no matter how they are allocated, the total time cannot be reduced further. | $i$ | **Base time $t_i$** | **Resources needed to reduce $1$ day $c_i$** | **Resources invested** | **Actual time** | |:-----:|:------------------:|:---------------------------:|:----------------:|:------------:| | $1$ | $6$ | $1$ | $1$ | $5$ | | $2$ | $5$ | ^ | $0$ | ^ | | $3$ | $6$ | $2$ | $2$ | ^ | | $4$ | $7$ | $1$ | ^ | ^ | ### Explanation for Sample 2 By investing $20$ units of resources, you can reduce the reclamation time of all regions to exactly $k = 2$ days. Due to the limit $k$, the remaining $10$ units of resources cannot reduce the time any further. ### Subtasks $70\%$ of the testdata satisfies: $0 < n, t_i, c_i \le 100$ and $0 < m \le 10^6$. All testdata satisfies: $0 < n, t_i, c_i \le 10^5$ and $0 < m \le 10^9$. Translated by ChatGPT 5