Problem Brief

Travel Distance on Scooters

FULLTIMENEW GRADOA

Imagine that you are standing at the starting point of a straight street and are trying to reach the end of the street. The street is represented by a number line starting at 0 and ending at finish, where finish > 0.

Electric scooters are scattered along the street. The array scooters stores their locations, where scooters[i] is the position of the i-th scooter. Each scooter can travel at most 10 points to the right before its battery is exhausted.

You must follow this exact algorithm:

From your current position, walk to the nearest scooter to your right. If there is no scooter to your right, walk directly to finish.
Ride that scooter as far as possible toward finish, using all of its remaining range.
If you have still not reached finish, repeat from step 1.

Return the total distance that you travel while riding scooters.

You are not required to provide the optimal asymptotic solution. A solution with time complexity no worse than O(scooters.length * finish) fits within the limit.

1Example 1

Input

finish = 23, scooters = [7, 4, 14]

Output

Explanation

From position 0, the nearest scooter to the right is at 4, so you ride from 4 to 14 for 10 scooter-distance. From 14, the next scooter to the right is at 14 itself, so you ride from 14 to 23 for 9 more. The total scooter distance is 19.

2Example 2

Input

finish = 27, scooters = [15, 7, 3, 10]

Output

Explanation

You first walk to the scooter at 3 and ride it to 13. Then the nearest scooter to the right is at 15, which takes you to 25. After that, there are no more scooters to the right, so you finish on foot. The scooter distance is 10 + 10 = 20.

3Example 3

Input

finish = 10, scooters = []

Output

Explanation

There are no scooters on the street, so you travel the entire route on foot and accumulate no scooter distance.

Constraints

Limits and guarantees your solution can rely on.

1 <= finish <= 1000
All scooter locations are distinct integers on the street.