Book Shop


Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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

There are no comments at the moment.