ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

H. Intelligence Data

Time limit: 1.0 second
Memory limit: 64 MB
It is a common conception that goblins are scary, filthy, unshaven, and hairy creatures. But it may come as a surprise to you that goblins love accuracy in everything. For example, if a goblin commander wants to know the average number of children of his subordinates, he will be given this number with any accuracy he wants. By the way, it is from goblins that Men took over the use of decimal fractions and the method of rounding numbers.
Brave Elvish scouts intercepted a report to the Chief goblin about the equipment of goblins' army. When Aragorn saw that there were 0.667 gold helmets, 1.444 charmed silver swords, and 0.778 mithril armours per one general, he understood at once that goblins had not eight (as it had been believed before), but at least nine generals.
The same report contained data about how many shields, boots, cauldrons, legs, and so on there were in the army per one soldier, per one brigadier, per one captain, etc. Using this information, Aragorn wants to determine the minimal possible numbers of soldiers, brigadiers, and goblins of other ranks in goblins' army.

Input

The first line contains the accuracy d (1 ≤ d ≤ 5) of data in the report and the number N of different averages given in the report for a certain group of goblins (1 ≤ N ≤ 100). The next N lines contain these averages. All the averages are positive and do not exceed one thousand; each of them is a fraction rounded exactly to d decimal digits.

Output

Output the minimal possible number of goblins in the given group.

Sample

inputoutput
2 3
52.29
0.71
170.86
7
Problem Author: Stanislav Vasilyev
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1539. Intelligence Data