After many years of searching, you have finally found \(N\) treasure conveniently labelled \(1\) to \(N\) buried on a deserted island. Each treasure \(i\) has a weight \(W_i\) and value \(V_i\).

Unfortunately, you only brought with you one knapsack which can carry treasures with a weight sum no more than \(K\).

Determine the maximum value of treasure you can carry.

\(1\le N\le 100\)

\(1\le K\le 10^8\)

\(1\le Wi, Vi\le 10^8\)

The first line will contain \(N\) and \(K\) separated by a space.

The next \(N\) lines each contain two space-separated integers. The \(i\)th line contains \(W_i\) and \(V_i\).

Output one integer, the maximum value of treasure you can carry.

`3 50`

10 60

20 100

30 120

`220`

- Points: 7
- Time limit: 1.0s
- Memory limit: 256.0M
- Author: BattleMage_
- Category: Classics
- Type: Dynamic Programming
- All Submissions Best Submissions