题目描述

小珅想用热气球运送一些物品，一共有 $n$ 个物品，第 $i$ 个的体积为 $v_i$，重量为 $w_i$。

小珅的热气球最多只能让重量为 $m$ 的物体顺利升空，要运送的物品都要装到热气球的吊篮中。小珅想要在顺利升空的前提下，运送总体积最多的物品，但是更大的体积意味着更大的吊篮，吊篮体积必须大于等于要运送的物品总体积。

小珅可以使用任意大小的吊篮，一个体积为 $V$ 的吊篮的重量是 $V\times c$。只有物品重量加吊篮的重量总和不超过 $m$ 时，气球才能顺利升空。

求出可以让小珅的气球升空的最大吊篮体积（这也是能运送的最大物品总体积）。

输入格式

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

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

输出格式

1 行，输出最大吊篮体积。如果无法让任何物品升空，输出 0。

样例输入

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

样例输出

25

提示

选第 2、5、6 个物品，体积 $V=25$，重量 $W=29$。加上吊篮后的总重量 $V\times c+W=79$，不超过 $m=80$。

$1\le n\le5000$，$1\le c\le10^6$，$1\le m\le\min(5000c,10^9)$，$1\le v_i\le5000$，$1\le w_i\le10^5$。

2 3 2
1 2
1 1

1

3 3333 36
102 173
37 68
14 129

51

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

25