Charm Bracelet Knapsack

Bessie has visited the mall's jewelry store and spotted a charm bracelet. Naturally, she wants to fill it with the best charms possible. There are \(N\) available charms and each charm \(i\) has a weight \(W_i\) and a desirability factor \(D_i\) and can be used at most once. Bessie can only support a bracelet whose total weight does not exceed \(M\).

Your task is to determine the maximum total desirability sum that can be achieved by selecting a subset of charms such that the total weight is at most \(M\). In mathematical terms, given \(N\) items with weights \(W_i\) and values \(D_i\) and a bag capacity of \(M\), compute:

\[ \max \sum_{i \in S} D_i \quad \text{subject to} \quad \sum_{i \in S} W_i \leq M \]

This is a classical 0/1 knapsack problem.

inputFormat

The first line contains two integers N and M separated by a space, where \(1 \le N \le 3402\) and \(1 \le M \le 12880\). Each of the following N lines contains two integers \(W_i\) and \(D_i\) separated by a space, representing the weight and desirability of the \(i\)-th charm, where \(1 \le W_i \le 400\) and \(1 \le D_i \le 100\>.

outputFormat

Output a single integer representing the maximum total desirability that can be achieved without exceeding the weight limit M.

sample

3 50
10 60
20 100
30 120

220