ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
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.


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 the minimal possible number of goblins in the given group.


2 3
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