Problem Statement

Bus Fare Minimization Problem Problem Description A city bus route has a stop at every single kilometer, and tickets are priced differently depending on how many of those 1-10 km stretches you cover in one ticket, so you can combine tickets cleverly to bring the total cost down for a longer trip. For example, take this list of fares for 1km through 10km: 12 21 31 40 49 58 69 79 90 101. With this list, the cheapest way to cover 15km costs 147: buy 1 ticket for a 3km stretch plus 2 tickets for 6km stretches. Given a fare list and a target distance, work out the cheapest total fare for covering that distance. Input: First line: 10 integers, the bus fare from 1km to 10km. Second line: The distance to move, N. Output: The minimum fare to travel the distance. Examples Example 1: Input: 12 21 31 40 49 58 69 79 90 101 15 Output: 147 Constraints 1 ≤ N ≤ 10000