Rod Cutting X71353

We have a rod of length L>0 that we can cut. The lenght unit is irrelevant (but you can choose centimeters if you need to). By cutting the rod, we will have a set of rods of possibly different lengths which will add up to L. We plan to enter a business of rod selling.

We have also a table with the prices of rods of all lengths up to L. For some mysterious reason beyond explanation (the world is full of such cases), the prices are not directly related to the lengths. This makes it a priori unclear whether it is better to sell a 4cm rod uncut, or two 2cm rods, or a rod of 1cm and another of 3cm, or three smaller rods of 1cm or 2cm...

As a specific case, suppose the following price table: 1cm: 10; 2cm: 24; 3cm: 30; 4cm: 40; 5cm: 45. What is the best way of cutting a 5cm rod?

Write a program that receives the length of our rod and the price table and computes the highest benefit that we can get from the sale of the cuts of our rod.

Even slow solutions may be easily accepted here. You are strongly advised to construct several solutions with different algorithmic schemes and different degrees of “smartness” and compare timings on yourself.

Input

First in the input comes the length L, a positive int; then, the price table: L floats for prices of rods of lengths 1 up to L.

Output

Write the maximum income that we can get by cutting the rod, as a float with two decimal places.