Draining the Rain Tank

A rain tank holds level litres (a whole number). Once per day the caretaker does exactly one of these:

• pump out one litre, or
• open valve d, for some d in the list valves, which is allowed only when the current level is divisible by d and leaves exactly level // d litres in the tank.

Write drain_days(level, valves) returning the fewest days needed to empty the tank.

Examples

Input:  level = 10, valves = [2, 3]
Output: 4
Explanation: pump to 9, valve 3 leaves 3, valve 3 leaves 1, pump to 0.

Input:  level = 10, valves = [2]
Output: 5
Explanation: 10 -> 5 -> 4 -> 2 -> 1 -> 0.

Input:  level = 7, valves = []
Output: 7

Constraints

• 0 <= level <= 10**18
• valves holds 0 to 9 distinct integers, each from 2 to 10
• Stepping through the levels one by one is far too slow.

Goals

• Prove that pumping is only worth doing just before a valve can open
• Recurse on level // d instead of stepping one litre at a time
• Memoise the small set of levels that the recursion actually reaches