← 返回题目列表

Codeforces · 808/E

E. 出售纪念品

中文机器翻译题面 查看原题

经过几项最新的改革,许多游客计划去贝尔兰旅游,贝尔兰人明白这是一个赚钱的机会,并改变了工作来吸引游客。例如,佩蒂亚离开了他一直工作的 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