CF808E.Selling Souvenirs

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```

首页