A vending hopper has a fixed volume of C units. There are n product types; type i occupies w_i units of volume and yields v_i profit per unit stocked. You have an unlimited supply of every type and may stock any type any number of times (including zero). Choose quantities so the total volume used is at most C and the total profit is maximized. Report that maximum profit (0 if nothing fits).
Input format
Line 1: two integers n and C.
Next n lines: two integers w_i and v_i for each product type.
Output format
A single integer: the maximum total profit for total volume at most C.
Constraints
- 1 <= n <= 40
- 0 <= C <= 5000
- 1 <= w_i <= 1000
- 1 <= v_i <= 1000