Charm Bracelet

Bessie is at the mall's jewelry store and spots a charm bracelet. She would like to fill it with the best possible selection from the $N$ ($1 \le N \le 3402$) available charms. Charm $i$ has a weight $W_i$ ($1 \le W_i \le 400$) and a desirability $D_i$ ($1 \le D_i \le 100$), and each charm may be used at most once. The bracelet can support a total weight of at most $M$ ($1 \le M \le 12880$).

Given the weight limit and the list of charms with their weights and desirabilities, determine the maximum possible sum of desirabilities.

• Line 1: two space-separated integers $N$ and $M$.
• Lines 2 to $N+1$: line $i+1$ contains two space-separated integers $W_i$ and $D_i$ describing charm $i$.

• A single integer: the greatest total desirability that can be achieved without exceeding the weight limit.

In the sample, the optimal choice skips the second charm. Picking the charms of weight $1$, $3$, and $2$ gives a desirability of $4 + 12 + 7 = 23$ for a total weight of $1 + 3 + 2 = 6$, which does not exceed the limit.