Knapsack
题号：NC213135
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Bobo has n items, where the i-th item has weight w_i and value v_i. He wants to pick some items whose sum of weights does not exceed m, and maximize the sum of values.

输入描述:

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m. The i-th of the following n lines contains two integers w_i and v_i.

* 
* 
* 
* 
* The sum of n does not exceed .
* The sum of m does not exceed .

输出描述:

For each test case, print an integer which denotes the result.
示例1

输入

复制 
3 4
1 1
2 2
2 3
3 5
1 1
2 2
2 3
1 10
9 1000000000

输出

复制 
5
6
1000000000