Lending a Hand to the Potter (B) X33098

Our beloved ladyfriend Coràlia Belet is a potter. She has now N handfuls of clay. Lately, she makes bowls of various sizes: with one handful of clay, with two, with three... per bowl, up to N when she makes the largest bowl. She has a list with the profits she obtains from selling each bowl size, from 1 to N; however, the profit from each bowl does not correspond well to how many handfuls of clay were employed for its making: big ones, besides requiring more clay, raise difficulties at the turning wheel, but it is also difficult, for different reasons, to make very small, yet goodlooking ones. She needs a piece of advice today: how must she distribute her N handfuls of clay to make bowls and reach the maximum profit? We want a program that helps her.

Example: with 5 handfuls of clay, and assuming that the profits in euros and cents are: 1: 25; 2: 60; 3: 75; 4: 100; and 5: 112.50, the highest profit is 145.00 euros; this is reached by making one bowl with 1 handful of clay and 2 bowls with 2 handfuls of clay each.

Input

Data start with N > 0: how many handfuls of clay must Coràlia distribute today. Follows the list of profits, N floats: how much does she make by selling a bowl made with k handfuls of clay, for k from 1 to N, expressed with two decimal places (euros and cents). These data come separated by spaces or tabs or ends of line, that is, they may, or may not, occur within the same input line.

Output

The highest profit Coràlia can make today, expressed with two decimal places: euros and cents. (The automatic correction will not want to see how that goal is reached. However, human eyes will check your program out and will value positively evidence that the program may be very easily changed into another one that does provide that extra information.)

Observation

Solve this problem following a backtracking algorithm scheme. The twin problem X52116 asks for solving exactly the same problem following a dynamic programming scheme.