Kittan is in charge of the battleship-like Dai-Gunzan and therefore is responsible for choosing which Gunmen should stay on Dai-Gunzan's deck to patrol. Kittan has possible Gunmen to choose from. Unfortunately, Kittan doesn't have the patience to carefully assess each individual Gunmen's capabilities, so he labels each as "Good" or "Bad", based on a cursory glance. He assigns a protection value of to "Good" Gunmen and to "Bad" Gunmen.

The deck of Dai-Gunzan has limited room — there are exactly units of space for patrolling Gunmen to use. Kittan is a busy man, so he assigned Jorgun to keep track of the amount of space each Gunmen takes up. He also assigned Balinbow to figure out the maximum sum of protection values Dai-Gunzan can have by taking a subset of available Gunmen whose total space consumption does not exceed . Unfortunately, while Jorgun is barely smart enough to measure Gunmen, Balinbow desperately needs your help in this optimization problem.

#### Input Specification

The first line of input will contain two integers and , separated by a single space.

The next lines of input will contain two integers and , the space and protection value of the Gunmen, respectively.

#### Output Specification

The first and only line of output should be the maximum protection value Dai-Gunzan can have.

#### Constraints

##### Subtask 1 [25%]

##### Subtask 2 [75%]

For all subtasks, .

#### Sample Input

```
5 11
1 1
6 2
3 1
5 2
4 2
```

#### Sample Output

`5`

#### Explanation

Take the Gunmen that use 1, 4, and 5 space for a total protection value of .

## Comments

I got quickscoped Barred from entering a solution :/ kek

http://www.dmoj.ca/tos/

LOL thanks, i noticed that in my submission. Didn't read the TOS and decided to be cheap, sorry about that. I don't know why my program didn't work for that one case..

I've deleted the offending submission. Don't do it again. Instead, figure out why your program doesn't work, fix it, and resubmit.

I'm stuck on this question.

Mod Edit: Do not post full solutions or algorithms in the comments.Idea : Try seperating the "good" gunmen and the "bad" ones

For N, M and S

Subtask 1 [25%]

1≤N,M,Si≤1000

Subtask 2 [75%]

1≤N,M,Si≤100000

For all subtasks, 1≤Pi≤2.

Does subtasks 2 include subtask 1?

Subtasks are disjoint, but they may share test cases. It all adds up to 100%.