Book Shop
A bookshop has \(n\) books on sale. For every book you know its price and how many pages it has.
Your budget is \(x\): the prices of the books you pick must add up to at most \(x\). Each book can be bought at most once. What is the largest total number of pages you can get?
Input Specification
The first line contains two integers \(n\) and \(x\): the number of books and your budget.
The second line contains \(n\) integers \(h_1, h_2, \dots, h_n\), where \(h_i\) is the price of book \(i\).
The third line contains \(n\) integers \(s_1, s_2, \dots, s_n\), where \(s_i\) is the number of pages of book \(i\).
Output Specification
Output a single integer: the maximum total number of pages you can buy without going over the budget.
Constraints
- \(1 \le n \le 500\)
- \(1 \le x \le 10^4\)
- \(1 \le h_i, s_i \le 1000\)
Sample Input
4 10
4 8 5 3
5 12 8 1
Sample Output
13
Explanation
Buying books 1 and 3 costs \(4 + 5 = 9 \le 10\) and gives \(5 + 8 = 13\) pages. No other choice within the budget gives more pages.
Comments