P2871 [USACO07DEC] Charm Bracelet S

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.

* 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$.

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

$1 \le N \le 3402$，$1 \le M \le 12880$，$1 \le W_i \le 400$，$1 \le D_i \le 100$。