There are items, numbered . For each , item has a weight of and a value of .

Taro has decided to choose some of the items and carry them home in a knapsack. The capacity of the knapsack is , which means that the sum of the weights of items taken must be at most .

Find the maximum possible sum of the values of items that Taro takes home.

#### Constraints

- All values in input are integers.

#### Input Specification

The first line of input will contain 2 space separated integers, and .

The next lines will contain 2 space separated integers, and , the weight and value of item .

#### Output Specification

You are to output a single integer, the maximum possible sum of the values of items that Taro takes home.

#### Sample Input 1

```
3 8
3 30
4 50
5 60
```

#### Sample Output 1

`90`

#### Sample Input 2

```
1 1000000000
1000000000 10
```

#### Sample Output 2

`10`

#### Sample Input 3

```
6 15
6 5
5 6
6 4
6 6
3 5
7 2
```

#### Sample Output 3

`17`

#### Sample Explanations

For the first sample, items and should be taken. Then, the sum of the weights is , and the sum of the values is .

For the third sample, items , , and should be taken. Then, the sum of the weights is , and the sum of the values is .

## Comments