Background

Luogu’s testdata is for community communication only and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

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.

Input Format

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.

Output Format

Write output to standard output.

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

4 9 2
6 1
5 1
6 2
7 1

5

4 30 2
6 1
5 1
6 2
7 1

2

Hint

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$		$5$
$2$	$5$	^	$0$	^
$3$	$6$	$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