Maximum Items With a One-Time Surcharge

You are given a fixed amount of money, budget, to spend at a shelf of items where item i has price costs[i]. You want to leave with as many items as possible; it does not matter which ones, only the count. Each item can be taken at most once.

Every item is one of two kinds, given by kinds[i]: regular (0) or special (1). If your cart contains any special items at all, a flat fee of surcharge is added once at checkout, no matter whether you take 1 special item or 50. A cart with no special items pays no fee.

So your bill is the sum of the prices of the items you take, plus surcharge if the cart contains at least one special item.

The bill must be at most budget. Return the largest number of items you can afford.

Examples

Example 1

Input: costs = [4, 2, 3, 5], kinds = [0, 1, 0, 1], budget = 10, surcharge = 1
Output: 3
Explanation: Take the items priced 2, 3 and 4. The item priced 2 is special, so the bill is 2 + 3 + 4 + 1 = 10 <= 10. No cart of 4 items fits the budget (the cheapest four cost 14 before the fee).

Example 2

Input: costs = [5, 1, 1], kinds = [0, 1, 1], budget = 6, surcharge = 10
Output: 1
Explanation: Any cart with a special item pays the fee of 10 and blows past the budget of 6; even the single item priced 1 would cost 1 + 10 = 11. The best cart is the one regular item priced 5.

Example 3

Input: costs = [2, 2, 2], kinds = [1, 1, 1], budget = 7, surcharge = 3
Output: 2
Explanation: Two items cost 2 + 2 = 4, plus the one-time fee of 3, for exactly 7. All three would cost 6 + 3 = 9 > 7. Note the fee is 3 whether you take one special item or two.