Before the servers shut down, the management launched a series of polls to investigate which game content left a deeper impression on players. As a loyal fan of the series, you want to know how many people participated in the pre-shutdown poll, but the management only disclosed the final results: for a poll containing $N$ options, the proportion of players who chose the $i$-th option is $P_i$ ($1 \le i \le N$). When the results were announced, the management rounded them, with all $P_i$ values kept to $L$ decimal places. Assuming there are actually $K$ players who participated in the poll, and $D_i$ players chose the $i$-th option, it should hold that:

$$P_i - \frac{1}{2} \times 10^{-L} \le \frac{D_i}{K} < P_i + \frac{1}{2} \times 10^{-L}$$

Obviously, all $D_i$ must be non-negative integers, and $K = \sum_{i=1}^N D_i$ must be a positive integer. Now, given $N$ and $P_i$, find the minimum total number of votes $K$ such that there exists a non-negative integer solution for $D_i$.

Input

Read data from standard input. The first line contains a positive integer $N$, representing the total number of options in the poll. It is guaranteed that $1 \le N \le 100$. The next $N$ lines each contain a real number $P_i$ in $[0, 1]$, representing the proportion of players who chose the $i$-th option. It is guaranteed that $\sum_{i=1}^N P_i = 1$, all $P_i$ are kept to $L$ decimal places, and $1 \le L \le 6$.

Output

Output to standard output. Output a single positive integer representing the minimum total number of votes $K$ that satisfies the requirements.

Examples

Input 1

3
0.166667
0.333333
0.500000

Output 1

6

Note 1

The minimum total number of votes is 6, corresponding to 1, 2, 3 votes for each option respectively.

Input 2

7
0.041096
0.109589
0.109589
0.164384
0.301370
0.068493
0.205479

Output 2

73

Note 2

The minimum total number of votes is 73, corresponding to 3, 8, 8, 12, 22, 5, 15 votes for each option respectively.

Input 3

11
0.001545
0.038759
0.015838
0.051893
0.080994
0.068246
0.156580
0.104043
0.026397
0.143317
0.312388

Output 3

7766

Note 3

The minimum total number of votes is 7766, corresponding to 12, 301, 123, 403, 629, 530, 1216, 808, 205, 1113, 2426 votes for each option respectively.

Subtasks

For 100% of the data, it is guaranteed that $1 \le N \le 100$, $0 \le P_i \le 1$, $\sum_{i=1}^N P_i = 1$, and $P_i$ are kept to at most 6 decimal places.