Problem C
Bölk
It’s time to bulk up for the gym, but to do that you have to go grocery shopping. Only two things matter when grocery shopping on a bulk: the price of the food and the calorie count. You want to get the most out of your food, so you want to get as many calories as possible without going over your budget.
There are $n$ food products in the store you are shopping. Each product has some price $v$ in Icelandic krónur and a calorie count $h$. You have the choice of either buying a product or not. You cannot buy more than one copy of the same product. You also cannot spend more than $c$ Icelandic krónur in total.
Input
The first line of the input contains two integers $n$ and $c$ ($1 \leq n, q \leq 10^3$). Then follow $n$ lines, each containing two integers $v$ and $h$ ($0 \leq v, h \leq 10^6$). Each of these lines correspond to a food product in the store that costs $v$ Icelandic krónur and $h$ calories.
Output
The output should include a single integer, the maximum amount of calories you can buy without spending more than $c$ Icelandic krónur in total.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 60 25 20 25 20 40 50 21 15 |
50 |
