悲伤的故事

由于现场出现了预料之外的做法。

因此现在是经过修改后的范围和数据，集训队互测现场的情况并没有参考价值。

如果你觉得你的做法空间正确且获得了 MLE，请尝试替换引用的头文件。

题目背景

Mayflower - Plum

五月和七月收拾好自己的东西，分别踏上了属于自己的路……

题目描述

请注意本题不常规的空间限制。

给定 $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, m, k$ 后，在满足 $r - l \leq k$ 的所有的数据中等概率随机选一组。