背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

顿顿总共选中了 $n$ 块区域准备开垦田地，由于各块区域大小不一，开垦所需时间也不尽相同。据估算，其中第 $i$ 块（$1 \le i \le n$）区域的开垦耗时为 $t_i$ 天。这 $n$ 块区域可以同时开垦，所以总耗时 $t_{Total}$ 取决于耗时最长的区域，即：

$$\begin{aligned} t_{Total} = \max\{t_1, t_2, \cdots, t_n\} \end{aligned}$$

为了加快开垦进度，顿顿准备在部分区域投入额外资源来缩短开垦时间。具体来说：

• 在第 $i$ 块区域每投入 $c_i$ 单位资源，便可将其开垦耗时缩短 $1$ 天；
• 耗时缩短天数以整数记，即第 $i$ 块区域投入资源数量必须是 $c_i$ 的整数倍；
• 在第 $i$ 块区域最多可投入 $c_i \times (t_i - k)$ 单位资源，将其开垦耗时缩短为 $k$ 天；
• 这里的 $k$ 表示开垦一块区域的最少天数，满足 $0 < k \le \min\{t_1, t_2, \cdots, t_n\}$；换言之，如果无限制地投入资源，所有区域都可以用 $k$ 天完成开垦。

现在顿顿手中共有 $m$ 单位资源可供使用，试计算开垦 $n$ 块区域最少需要多少天？

输入格式

从标准输入读入数据。

输入共 $n + 1$ 行。

输入的第一行包含空格分隔的三个正整数 $n$、$m$ 和 $k$，分别表示待开垦的区域总数、顿顿手上的资源数量和每块区域的最少开垦天数。

接下来 $n$ 行，每行包含空格分隔的两个正整数 $t_i$ 和 $c_i$，分别表示第 $i$ 块区域开垦耗时和将耗时缩短 $1$ 天所需资源数量。

输出格式

输出到标准输出。

输出一个整数，表示开垦 $n$ 块区域的最少耗时。

4 9 2
6 1
5 1
6 2
7 1

5

4 30 2
6 1
5 1
6 2
7 1

2

提示

样例 1 解释

如下表所示，投入 $5$ 单位资源即可将总耗时缩短至 $5$ 天。此时顿顿手中还剩余 $4$ 单位资源，但无论如何安排，也无法使总耗时进一步缩短。

$i$	基础耗时 $t_i$	缩减 $1$ 天所需资源 $c_i$	投入资源数量	实际耗时
$1$	$6$	$1$		$5$
$2$	$5$	^	$0$	^
$3$	$6$	$2$
$4$	$7$	$1$	^

样例 2 解释

投入 $20$ 单位资源，恰好可将所有区域开垦耗时均缩短为 $k = 2$ 天；受限于 $k$，剩余的 $10$ 单位资源无法使耗时进一步缩短。

子任务

$70\%$ 的测试数据满足：$0 < n, t_i, c_i \le 100$ 且 $0 < m \le 10^6$；

全部的测试数据满足：$0 < n, t_i, c_i \le 10^5$ 且 $0 < m \le 10^9$。