0/1 Knapsack

Medium#dynamic-programming· solved by 0 · time limit 2.0 s

You have $n$ items with weights and values and a bag that holds weight at most $W$ . Each item can be taken at most once. Maximise the total value.

Input

$n$ and $W$ , then $n$ lines weight value.

The maximum value.

$1 \le n \le 100$ , $1 \le W \le 10^4$

Input

Output