A commuter knows the days they will ride the city train, given as the strictly increasing list days. The ticket office sells several kinds of pass, passes[k] = (length, price): a pass bought for day d is valid on days d, d + 1, ..., d + length - 1. Any number of passes of any kind may be bought. Return the minimum total price that covers every travel day.
Examples
Input: days = [1, 3, 4, 5, 9, 20], passes = [(1, 3), (5, 10)]
Output: 16
Explanation: a 5-day pass for days 1-5 (10), then single-day passes for days 9 and 20 (3 + 3).
Input: days = [2], passes = [(1, 5), (30, 2)]
Output: 2
Explanation: a longer pass can be cheaper than a short one.
Constraints
1 <= len(days) <= 10**5,1 <= days[i] <= 10**6, strictly increasing1 <= len(passes) <= 5,1 <= length <= 10**6,1 <= price <= 10**4- Target complexity: O(n * p * log n) or better; trying every combination of passes is exponential.
Goals
- Index the dp by travel day rather than by calendar day
- Jump to the first travel day a pass no longer covers