Selling Souvenirs

题意翻译

## 题目背景 Berland经过了多次改革后，许多游客打算来这儿游玩。居民们知道这是一个改行旅游服务业来赚钱的好机会，Petya也离开了他以前工作的IT公司，改在市场买礼品了。 ## 题目描述 像平常一样，今早Petya回来到市场。他有 $n$ 个不同的礼品要卖；第 $i$ 个礼品有重量 $w_{i}$ 和价格 $c_{i}$ 两个属性。Petya知道他不能把所有礼品扛到市场，便想要选一部分总重量不超过 $m$ 的礼品，而总价格越高越好。 帮帮Petya确定最大的总价格吧。 ## 输入输出格式 ### 输入格式： 第一行包括两个整数 $n$ 和 $m$（$1<=n<=100000$ , $1<=m<=300000$）——Petya的礼品数量和他能带去市场的最大重量。 然后下面$n$行中第$i$行各有两个整数 $w_{i}$ 和 $c_{i}$（$1<=w_{i}<=3$ , $1<=c_{i}<=10^{9}$）——第 $i$ 个礼品的重量和价格。 ### 输出格式： 输出一个数字——Petya能带去的礼品的最大总价格。

题目描述

After several latest reforms many tourists are planning to visit Berland, and Berland people understood that it's an opportunity to earn money and changed their jobs to attract tourists. Petya, for example, left the IT corporation he had been working for and started to sell souvenirs at the market. This morning, as usual, Petya will come to the market. Petya has $ n $ different souvenirs to sell; $ i $ th souvenir is characterised by its weight $ w_{i} $ and cost $ c_{i} $ . Petya knows that he might not be able to carry all the souvenirs to the market. So Petya wants to choose a subset of souvenirs such that its total weight is not greater than $ m $ , and total cost is maximum possible. Help Petya to determine maximum possible total cost.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=100000 $ , $ 1<=m<=300000 $ ) — the number of Petya's souvenirs and total weight that he can carry to the market. Then $ n $ lines follow. $ i $ th line contains two integers $ w_{i} $ and $ c_{i} $ ( $ 1<=w_{i}<=3 $ , $ 1<=c_{i}<=10^{9} $ ) — the weight and the cost of $ i $ th souvenir.

输出格式

Print one number — maximum possible total cost of souvenirs that Petya can carry to the market.

输入输出样例

输入样例 #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