Buying books
There are
n books in the store. You know the prices and the number of pages for each of the books. You have x dollars in your pocket, so you can’t spend more than x. What is the maximum number of pages you can buy? Note that you can buy each book only once.Input
The first line of the input contains two integers
n (1 ≤ n ≤ 100) and x (1 ≤ x ≤ ).The next line contains
n space-separated integers The third line contains
n space-separated integers Output
The program should print the maximum number of pages you can buy with
x.Examples
Input | Output |
4 10
4 8 5 3
5 12 8 1 | 13 |
Explanation
You can buy the first and the third books. The cost will be
4 + 5 = 9, while the number of pages will be 5 + 8 = 13.Constraints
Time limit: 7 seconds
Memory limit: 512 MB
Output limit: 1 MB