Thematic Park Group Tickets (DP) X46212

The thematic park of Tort Apenvura is setting up a complex scheme of group tickets, whose prices will depend on the size of the group; but they tried to take into account specific factors such as the sizes of the tables at the restaurants and the simultaneous capacity of various attractions, so that the prices do not have really a correlation with the group size. As they are unsure whether to deploy the plan, they have hired our friend, the free-lance consultant Mar Talavera, for advice. She has understood that, with this scheme, maybe a group of N people, instead of paying their set price for a group of N, might try and split into several smaller groups so as to pay less in total.

She has the proposed list of prices for all the group sizes from 1 to N persons. What would be the least expensive way for N persons to get in?

For example, assume that the prices per group size, in euros and cents, are: 1: 25.50; 2: 45; 3: 68; 4: 99.50; and 5: 130. Then, although a group of 5 is asked to pay 130, these 5 people can get in paying individual tickets for 5*25.50 = 127.50, or make two pairs and a single ticket for 115.50 or, even better, split into a group of 2 and a group of 3 and pay only 113, which is, actually, the cheapest cost for the group of 5.

Input

Data start with N > 0: the maximum group size for which the price system applies. In the next line follows the list of prices, N floats: how much is a group of k people asked pay, for k from 1 to N, expressed with two decimal places (euros and cents). These values come separated by spaces in a single input line.

Output

The cost of the cheapest way for N people to enter, expressed with two decimal places: euros and cents. (The automatic correction will not want to see how the group is split so that the cheapest cost is reached. However, human eyes that might check your program out would be likely to value positively evidence that the program may be very easily changed into another one that does provide that extra information.)

Observation

You must use a dynamic programming scheme to solve this problem. Problem X55205 asks for a backtracking solution to the same statement.