Pokemon Trading

Time limit0.3sMemory limit4 MB

Summary

With a fixed budget, buy on one day and sell on a later day to maximize profit; report the best result rounded to two decimals.

Level: Medium4 of 10
Topics: Array, Greedy, Math
Solved: No attempts yet

Problem

Jim likes Pokemon and plays every game they appear in. The game he plays now is a trading game. Jim already knows the price of a Pokemon on each of the next $n$ days. The type does not matter, so a single price applies to every Pokemon on a given day.

Jim starts with a fixed amount of money. He picks one day and spends all of his money buying Pokemon on that day, then picks a later day and sells all of them. Fractional Pokemon can be bought. The selling day must come after the buying day.

Find the largest profit Jim can get. If every choice loses money, find the smallest loss.

Input

The first line contains the amount of money Jim has.

The second line contains the number of days $n$ . ( $1 < n \le 10^6$ )

Starting from the third line, $n$ prices are given in day order, separated by spaces.

The money and every price are positive real numbers of at most $10^9$ with at most 6 digits after the decimal point.

Output

Print the maximum profit on the first line, with 2 digits after the decimal point. The value is negative when Jim loses money.

Rounding goes away from zero. That is, $0.005$ becomes 0.01, $0.0049$ becomes 0.00, $-0.005$ becomes -0.01, and $-0.0049$ becomes -0.00. When the profit is less than $0$ but its rounded magnitude is $0$ , print -0.00.

Examples4

Example 1
Input
```
100.7
5
1 2.88 3.05 4.33 5.5
```
Expected output
```
453.15
```
Example 2
Input
```
100
2
5 4
```
Expected output
```
-20.00
```
Example 3
Input
```
1000
3
7 7 7
```
Expected output
```
0.00
```
Example 4
Input
```
1
2
1 0.999999
```
Expected output
```
-0.00
```