悲伤的故事
由于现场出现了预料之外的做法。
因此现在是经过修改后的范围和数据，集训队互测现场的情况并没有参考价值。
如果你觉得你的做法空间正确且获得了 MLE，请尝试替换引用的头文件。
题目背景
五月和七月收拾好自己的东西，分别踏上了属于自己的路……
题目描述
请注意本题不常规的空间限制。
给定 $n$ 个物品，体积依次为 $v_1, v_2, \dots, v_n$，价值依次为 $w_1, w_2, \dots, w_n$。
你需要从中选择一些物品，保证体积和不超过 $m$。你将会带走你选择的物品，你的收益是这些物品的价值和。输出你的收益的最大值。
特别地，有一个每次给定的系数 $k$，数据保证如下性质：
- 如果你可以先选定一个元素都在 $(0, 1]$ 之间的实数序列 $p_1, p_2, \dots, p_n$。并对于所有物品，第 $i$ 个物品的体积和价值同时乘以 $p_i$，即体积变为 $p_iv_i$，价值变为 $p_iw_i$。然后你再进行选择物品，那么你的收益最多为 $r$。
- 在原问题中，假设你的收益最多为 $l$，则有 $r-l\leq k$。
输入格式
第一行三个正整数 $n, m, k$。
接下来 $n$ 行，第 $i$ 行两个正整数 $v_i, w_i$。
输出格式
一行一个数，表示答案。
样例 0
样例 0 输入
8 20 6
10 6
9 8
6 3
2 5
6 8
3 8
1 9
4 2样例 0 输出
33附加样例 1~7
见附件下载中的 ex_mayflower1~7.in 与 ex_mayflower1~7.out。
附加样例依次满足本题的 $7$ 个子任务的限制。
样例解释
在题面中给定的样例中，$r$ 可以通过如下方式计算：
- 令 $p = [1, \frac 8 9, 1, 1, 1, 1, 1, 1]$，即对于第 $2$ 个物品，将其体积变为 $8$，价值变为 $\frac {64} 9$，其他物品不变。然后选取第 $2, 4, 5, 6, 7$ 这五个物品。此时总体积为 $8+2+6+3+1=20$，总价值为 $r = \frac {64} 9 + 5 + 8 + 8 + 9 = \frac {334} 9$。可以证明找不出更大的 $r$。
而 $l$ 可以通过如下方式计算：
- 选取第 $2, 5, 6, 7$ 这四个物品。此时总体积为 $9+6+3+1=19$，总价值为 $l = 8 + 8 + 8 + 9 = 33$。可以证明找不出更大的 $l$。
最终我们有 $r - l = \frac {37} 9$，又有 $k = 6$，满足 $r - l \leq k$。
数据范围
对于所有数据，保证 $1 \leq n \leq 10^4, 1 \leq m \leq 10^9, 1 \leq k \leq 20, 1 \leq v_i \leq 5000, 1 \leq w_i \leq 10^{12}$。
| 子任务编号 | $n \leq$ | $m \leq$ | $k \leq$ | $v_i \leq$ | $w_i \leq$ | 数据随机 | 分值 |
|---|---|---|---|---|---|---|---|
| 1 | $1000$ | $10^5$ | $20$ | $1000$ | $10^{12}$ | 否 | 5 |
| 2 | $1000$ | $10^9$ | $20$ | $1000$ | $10^{12}$ | 否 | 5 |
| 3 | $10^4$ | $10^9$ | $20$ | $333$ | $333$ | 否 | 10 |
| 4 | $10^4$ | $10^9$ | $1$ | $2000$ | $10^{12}$ | 否 | 20 |
| 5 | $10^4$ | $10^9$ | $5$ | $2000$ | $2000$ | 是 | 15 |
| 6 | $10^4$ | $10^9$ | $20$ | $2000$ | $2000$ | 是 | 15 |
| 7 | $10^4$ | $10^9$ | $20$ | $5000$ | $10^{12}$ | 否 | 30 |
数据随机：对于每组数据，给定 $n, m, k$ 后，在满足 $r - l \leq k$ 的所有的数据中等概率随机选一组。