Minimize Points Used Across Multiple Reward Programs

Problem

A customer has several reward programs. Program i has at most balance[i] points, and each point is worth value[i] integer microdollars. Given a target in microdollars, return the minimum total number of points whose combined value is at least the target, or -1 if the available points cannot cover it.

Constraints & Assumptions

• There are between 1 and 100 reward programs.
• Balances are nonnegative integers and values are positive integers.
• All inputs and intermediate products stay within 2^53.
• Points are indivisible and each program's balance is a hard upper bound.

Clarifications

• Overpaying the target is allowed; the primary objective is fewest points.
• Any combination with the minimum point count is acceptable, so return only that count.
• Exchange values are already fixed for the transaction date.

Examples

target = 168_000_000
balance = [36_000, 12_000, 25_000]
value = [12_000, 9_000, 8_500]
output = 14_000
explanation: 14,000 points at 12,000 microdollars each reach the target.

Hints