题目描述

在遥远的仙女座星系，小珅和小泽承接了一项星际物流任务。他们需要驾驶一艘反重力货运飞船，将一批珍贵的星尘矿石运往空间站。

这批货物共有 n 箱，第 i 箱星尘的体积为 $v_i$，质量为 $w_i$。飞船配备了一个特殊的“自适应吊舱”，其自重与装载容积直接相关。根据飞船核心的设定，若要启用一个容积为 V 的吊舱，该吊舱自身的空载质量恒定为 $V \times c$。

小泽作为飞船驾驶员，必须严格遵守飞船的载重上限。飞船的推进系统最多只能承受 m 的总质量（包含吊舱自身质量与所有货物的质量）。小珅作为货物管理员，希望在安全起飞的前提下，尽可能多地运输星尘。

由于吊舱的容积 V 必须至少等于所载货物的总体积，且吊舱大小可以任意定制，请你帮助小珅和小泽计算出：在保证飞船顺利升空（总质量 ≤ m）的情况下，所能使用的吊舱最大容积 V 是多少？这同时也代表了能够运送的星尘最大总体积。

输入格式

第 1 行，3 个正整数 n, m, c。

接下来 n 行，每行两个正整数 $v_i, w_i$。

输出格式

输出一行，一个整数，表示最大吊舱体积。 如果无法让任何物品升空（即连最小的合法配置都超重），输出 0。

输入输出样例

6 80 2
6 12
11 14
7 18
5 14
4 7
10 8

25

1 200 2
100 1

0

5 886 2
55 44
98 739
36 582
89 822
14 992

91

10 586019 1440
7 7
98 8
22 4
33 6
53 9
44 4
66 9
93 10
5 3
3 3

402

说明/提示

【数据范围】

$1 \le n \le 5000$ $1 \le c \le 10^6$ $1 \le m \le \min(5000 \times c, 10^9)$ $1 \le v_i \le 5000$ $1 \le w_i \le 10^5$