A spelunker's satchel can hold at most C grams. In the cavern lie n gems; gem i weighs w_i grams and is worth v_i coins. Each gem may be taken at most once. Choose a subset of gems whose total weight is at most C so that their total value is as large as possible. Report that maximum total value (0 if nothing can be taken).
Input format
Line 1: two integers n and C.
Next n lines: two integers w_i and v_i for each gem.
Output format
A single integer: the maximum total value of a subset with total weight at most C.
Constraints
- 1 <= n <= 40
- 0 <= C <= 2000
- 1 <= w_i <= 1000
- 1 <= v_i <= 1000