Number of Participants

Time limit2sMemory limit128 MB

Summary

Given N truncated (to 3 decimals) average scores from a survey with integer answers 0-10, find the smallest possible number of participants consistent with all averages.

Level: Medium5 of 10
Topics: Math, Brute force, Number theory
Solved: No attempts yet

Problem

Yujin is conducting a street survey. The survey has N questions, and each participant answers every question with an integer score from 0 to 10, inclusive.

After the survey, Yujin wrote down, for each question, the average score after discarding all digits after the third decimal place. For example, if three people answered one question with scores 4, 6, and 10, the true average is 6.666..., so the written value is 6.666.

Only these written average scores are known. Determine how many people participated in the survey. If multiple participant counts are possible, output the smallest one.

Input

The first line contains N.

Each of the next N lines contains the written average score for one question.

N is a positive integer not greater than 50. Each average is a decimal number between 0 and 10, inclusive, and is always given with exactly three digits after the decimal point.

Output

Print the number of people who participated in the survey. If there is more than one possible answer, print the smallest possible value.

Examples4

Example 1
Input
```
3
0.500
0.250
0.125
```
Expected output
```
8
```
Example 2
Input
```
1
0.000
```
Expected output
```
1
```
Example 3
Input
```
2
0.500
0.300
```
Expected output
```
10
```
Example 4
Input
```
2
0.500
0.301
```
Expected output
```
106
```