You are driving down a very long highway, with gas stations at mile-posts m₀, m₁,…,m_n, where m₀=0 is your starting point and m_n is your final destination. You want to make as few gas stops as possible, but your car can only hold enough gas to cover M miles. We want to find the minimum number of stops you need to make, as well as the gas stations where wou will refill your car.

Assignment

Write a Python function findStops which takes the volume M of your tank and a list of gas stations as parameter. The function returns the number of stops you need and a list of gas station where you will refill.

Example

>>> findStops(300, [0, 100, 200, 250, 330, 430, 500, 550, 600, 750, 900])
(3, [250, 550, 750])