Ordinary Knapsack

Interview

Time limit2sMemory limit512 MB

Summary

Given N items with weights and values, pick a subset with total weight at most K to maximize total value.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Junseo enlists in a month. He wants to take one trip before then, and since he will be away from the world for a while he wants to enjoy the trip as much as he can, so he packs his backpack for the highest possible value.

Junseo has $N$ items he thinks he needs for the trip. Each item has a weight $W$ and a value $V$ , and carrying that item in the backpack lets Junseo enjoy the trip by $V$ . Junseo has never marched before, so he can only carry a backpack whose packed weight sums to at most $K$ .

There is only one copy of each item, so the only choice per item is to pack it or leave it. Find the largest total value of the items Junseo can pack.

Input

The first line contains the number of items $N$ and the weight $K$ that Junseo can bear. ( $1 \le N \le 100$ , $1 \le K \le 100{,}000$ )

Each of the next $N$ lines contains the weight $W$ and the value $V$ of one item. ( $1 \le W \le 100{,}000$ , $0 \le V \le 1{,}000$ )

Every number in the input is an integer.

Output

Print the largest total value of the items that can be packed, on one line.

Examples3

Example 1
Input
```
4 7
6 13
4 8
3 6
5 12
```
Expected output
```
14
```
Example 2
Input
```
3 10
6 7
5 5
5 5
```
Expected output
```
10
```
Example 3
Input
```
1 1
2 1000
```
Expected output
```
0
```