Problem Description

joisino's next job is to rewrite documents.
There are $ N $ documents, each with a specified importance and time required for rewriting.
joisino really wants to leave on time, so she only has $ M $ hours left for work.
Therefore, joisino wants to maximize the total importance of the documents she can rewrite within the time limit, and decided to write a program to find this maximum value.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ V_1 $ $ T_1 $ $ V_2 $ $ T_2 $ : $ V_N $ $ T_N $

• The first line contains the number of documents $ N(1≦N≦500) $ and the remaining time $ M(1≦M≦500) $.
• The next $ N $ lines contain the importance $ V_i(1≦V_i≦10^5) $ and the time required for rewriting $ T_i(1≦T_i≦500) $ for the $ i $-th document.

Output Format

Output the maximum total importance of the documents that can be rewritten within the time limit on a single line.

Sample Input and Output

Sample Input #1

3 3
1 2
6 1
4 1

Sample Output #1

10

Sample Input #2

10 10
92231 7
70370 1
4423 10
96481 4
69142 2
91784 3
16328 3
85936 8
93166 2
17394 1

Sample Output #2

351801

Notes/Hints

Sample Explanation 1

Rewrite the 2nd and 3rd documents.

见题面 Input 部分

见题面 Output 部分