问题描述

顿顿总共选中了 $n$ 块区域准备开垦田地。第 $i$ 块区域的基础开垦耗时为 $t_i$ 天。所有区域可以同时开垦，因此在不投入额外资源的情况下，总耗时为

顿顿可以向部分区域投入有限的资源以缩短各自的耗时，规则如下：

• 在第 $i$ 块区域每投入 $c_i$ 单位资源，可以将该区域的耗时缩短 $1$ 天；
• 缩短天数必须为整数，因此在第 $i$ 块区域投入的资源量必须是 $c_i$ 的整数倍；
• 在第 $i$ 块区域最多可以投入 $c_i\times(t_i-k)$ 单位资源，将其耗时缩短到 $k$ 天；这里的 $k$ 是题目给定的全局下界，满足 $0\le k\le\min\{t_1,\dots,t_n\}$；即即使资源充足，每块区域的耗时也不能低于 $k$ 天。

现有总资源 $m$ 单位（不可分割的整数单位资源），请问在合理分配这些资源的前提下，开垦 $n$ 块区域最少需要多少天？

输入格式

共 $n+1$ 行：

• 第一行包含三个正整数 $n,;m,;k$，分别表示区域数量、可用资源总量和每块区域的最少开垦天数。

• 接下来 $n$ 行，第 $i$ 行包含两个正整数 $t_i,;c_i$，分别表示第 $i$ 块区域的基础耗时和每缩短 $1$ 天所需的资源量。

• $0 < n,t_i,c_i \le 10^5$；

• $0 < m \le 10^9$；

输出格式

输出一行，包含一个整数，表示在资源总量为 $m$ 的情况下，开垦 $n$ 块区域所能达到的最小总耗时（即完成所有区域所需的最少天数）。

样例输入 1

4 9 2
6 1
5 1
6 2
7 1

样例输出 1

5

样例输入 2

4 30 2
6 1
5 1
6 2
7 1

样例输出 2

2

说明

样例 1 解释

可以按下表分配资源使总耗时为 $5$ 天（剩余资源无法再进一步降低最大耗时）：

共投入 $1+0+2+2=5$（示例中输入为 $9$，仍有剩余）。

样例 2 解释

投入 $20$ 单位资源可以将所有区域都降到 $k=2$ 天（每块最多降到 $k$），此后受限于 $k$ 无法再降低。