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.