Description

Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the $N (1 \le N \le 3,402)$ available charms. Each charm i in the supplied list has a weight $W_i (1 \le W_i \le 400)$, a 'desirability' factor $D_i (1 \le D_i \le 100)$, and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than $M (1 \le M \le 12,880)$.

Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.

Input Format

• Line $1$: Two space-separated integers: $N$ and $M$.

• Lines $2 \sim N+1$: Line $i+1$ describes charm $i$ with two space-separated integers: $W_i$ and $D_i$.

Output Format

• Line $1$: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints.

4 6
1 4
2 6
3 12
2 7

23