你被给出了一个经典的背包问题：给定一组元素 $(w_1, v_1), \dots, (w_n, v_n)$ 和一个容量 $W$。求解 $$\max_{\substack{S \subseteq [n] \\ \sum_{i \in S} w_i \le W}} \sum_{i \in S} v_i$$ 这里 $[n]$ 是从 1 到 $n$ 的整数列表。

保证 $0 \le n \le 500$，$0 \le w_i \le W \le 10^{17}$，且 $0 \le v_i \le 10^{16}$。此外，保证 $w_i$ 已经按照下述段落进行了“平滑”处理。

一个符合上述界限的题目实例被构造出来。然后，一个随机化过滤器被应用于该题目实例，具体如下：令 $B$ 为最大重量元素的重量。现在，对每个重量应用以下更新： $$w_i \leftarrow \min(w_i + \text{rand}(\lfloor .05B \rfloor), W)$$ 这里 $\text{rand}(A)$ 是一个生成 $[0, A-1]$ 范围内均匀随机整数的函数。此过程仅应用于 $w_i$，而不应用于 $W$ 或任何其他值。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $W$。接下来的 $n$ 行，每行包含两个空格分隔的整数 $w_i$ 和 $v_i$。元素重量是按照上述方式生成的。首先，物品的选择符合所有界限，然后应用平滑算法。结果即为你的程序将接收到的输入。

输出格式

输出一行，表示给定背包问题实例的值。

样例

样例输入 1

3 5
1 2
2 3
3 4

样例输出 1

7

样例输入 2

3 302000
100588 2
200421 1000
30036 1

样例输出 2

1002