Charm Bracelet

Interview

Time limit1sMemory limit128 MB

Summary

Choose a subset of N charms, each with a weight and a desirability, so that total weight stays within M and total desirability is maximized.

Level: Medium5 of 10
Topics: Dynamic programming, Array, Greedy, Brute force
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Hint

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.

Examples3

Example 1
Input
```
4 6
1 4
2 6
3 12
2 7
```
Expected output
```
23
```
Example 2
Input
```
1 1
1 100
```
Expected output
```
100
```
Example 3
Input
```
1 5
6 42
```
Expected output
```
0
```