You are packing a bag that can carry at most a fixed total weight cap. There are n items; item i has an integer weight w_i and an integer value v_i. Each item may be taken at most once (you either pack the whole item or leave it — no fractions).
Choose a subset of items whose combined weight does not exceed cap and whose combined value is as large as possible. Report that maximum total value.
Input format
Line 1: two integers n and cap.
The next n lines: each contains two integers w_i and v_i — the weight and value of item i.
Output format
A single integer: the maximum total value achievable without exceeding the capacity. If no item fits (for example when cap is 0), the answer is 0.
Constraints
- 1 ≤ n ≤ 200
- 0 ≤ cap ≤ 2000
- 1 ≤ w_i ≤ 2000
- 0 ≤ v_i ≤ 100000
- The empty selection is always allowed and has value
0.