经过几项最新的改革,许多游客计划去贝尔兰旅游,贝尔兰人明白这是一个赚钱的机会,并改变了工作来吸引游客。例如,佩蒂亚离开了他一直工作的 IT 公司,开始在市场上出售纪念品。
今天早上,像往常一样,Petya 会来到市场。 Petya有n种不同的纪念品可供出售;第 i 个纪念品的特征在于其重量 wi 和成本 ci。佩蒂亚知道他可能无法将所有纪念品带到市场。因此 Petya 希望选择一个纪念品子集,使其总重量不大于 m,并且总成本尽可能最大。
帮助 Petya 确定最大可能的总成本。
输入
第一行包含两个整数 n 和 m (1 ≤ n ≤ 100000, 1 ≤ m ≤ 300000) — Petya 的纪念品数量和他可以携带到市场的总重量。
接下来是 n 行。第 i 行包含两个整数 wi 和 ci (1 ≤ wi ≤ 3, 1 ≤ ci ≤ 109) — 第 i 个纪念品的重量和成本。
输出
打印一个数字 — Petya 可以携带到市场的纪念品的最大可能总成本。
示例
输入 #1
1 1 2 1
输出 #1
0
输入 #2
2 2 1 3 2 2
输出 #2
3
输入 #3
4 3 3 10 2 7 2 8 1 1
输出 #3
10