Cramming

Interview

Time limit2sMemory limit256 MB

Summary

Given N chapters, each with a study time and a score, choose a subset whose total study time fits in T to maximize the total score.

Level: Easy3 of 10
Topics: Dynamic programming, Array, Greedy, Brute force
Solved: No attempts yet

Problem

Junseok became the president of ChAOS (Chung-ang Algorithm Organization and Study), the work piled up, and he never got around to studying during the exam period. Now it is the night before the exam. The professor did post two hints beforehand.

No question mixes several chapters.
Each chapter gets exactly one question. That question can only be solved by someone who knows everything in the chapter.

The professor also wrote down the score of each chapter next to the hints. Assume Junseok gets a chapter's question right if he studies that chapter for its estimated study time or longer. A chapter is either studied or not studied, and there is no partial credit.

Find the highest total score Junseok can reach with the time he has left.

Input

The first line contains the number of chapters on the exam $N$ ( $1 \le N \le 100$ ) and the total time available before the exam $T$ ( $1 \le T \le 10000$ ), separated by a space.

Each of the next $N$ lines contains the estimated study time $K$ ( $1 \le K \le 1000$ ) of one chapter and the score $S$ ( $1 \le S \le 1000$ ) of that chapter's question, separated by a space.

Output

Print the highest score Junseok can get on the first line.

Examples6

Example 1
Input
```
3 310
50 40
100 70
200 150
```
Expected output
```
220
```
Example 2
Input
```
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
1 1
1000 1
```
Expected output
```
0
```
Example 4
Input
```
3 10
6 10
5 6
5 6
```
Expected output
```
12
```
Example 5
Input
```
3 10
10 10
6 7
4 7
```
Expected output
```
14
```
Example 6
Input
```
3 100
30 1
70 1
100 10
```
Expected output
```
10
```