A shop has n books. Book i costs prices[i] and has pages[i] pages. You can buy each book at most once, and the total price must not exceed budget. Return the largest total number of pages you can get.
Implement book_shop(prices: list[int], pages: list[int], budget: int) -> int.
book_shop([4, 8, 5, 3], [5, 12, 8, 1], 10) # 13 books 0 and 2: price 9, pages 5 + 8
book_shop([7], [100], 6) # 0 can't afford anything
Constraints: 1 <= n <= 100, 1 <= budget <= 5000, 1 <= prices[i], pages[i] <= 1000.
Trying all 2^n subsets is exponential; aim for O(n × budget).
Show hint
track the most pages you can get for each possible total spend, adding one book at a time. Make sure a single book can't be counted twice while you do.