Season tickets

You know the days on which you will travel by train: days, a rising list of different whole numbers. The railway sells passes, given as (length, price): a pass bought on day d lets you travel on days d, d + 1, …, d + length − 1. You may buy any pass any number of times. Return the least total price that lets you travel on every day in days.

season_tickets([1, 4, 6, 7, 8, 20],
               [(1, 2), (7, 7), (30, 15)])
# 11: a 1-day ticket on day 1, a 7-day pass
# from day 4 (covers 4 to 10), a 1-day on day 20

Limits

• Up to 100,000 travel days, each from 1 to 2,000,000,000; up to 6 passes, each with a length of at least 1. A table with one entry per calendar day is far too big.
• Aim for about O(n · p · log n) for n trips and p passes. bisect is allowed.
• Python stops at about 1,000 nested calls, and a function wrapped in functools.cache stops after a few hundred in the browser. The big tests need far more than that, so memoised recursion fails them. Fill a table with a loop (lesson 3).