描述：

A burglar got into a matches warehouse and wants to steal as many matches as possible. In the warehouse there are m containers, in the i-th container there are ai matchboxes, and each matchbox contains bi matches. All the matchboxes are of the same size. The burglar's rucksack can hold n matchboxes exactly. Your task is to find out the maximum amount of matches that a burglar can carry away. He has no time to rearrange matches in the matchboxes, that's why he just chooses not more than n matchboxes so that the total amount of matches in them is maximal.

输入：

The first line of the input contains integer n (1 ≤ n ≤ 2·108) and integer m (1 ≤ m ≤ 20). The i + 1-th line contains a pair of numbers ai and bi (1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10). All the input numbers are integer.

输出：

Output the only number — answer to the problem.

翻译

描述

一个窃贼进入了一间火柴仓库，并且想要尽可能多地带走火柴。在这个火柴仓库中有m个箱子，第i个箱子里面有ai个火柴盒，每个火柴盒中有bi根火柴。所有的火柴盒形状大小都相同，窃贼的背包最多能放下n个火柴盒。你的任务是求出窃贼能带走的火柴的最大数量。窃贼没有时间来整理背包中的火柴，这也是他只拿n个火柴盒的原因。

输入

输入的第一行包括整数n(1 ≤ n ≤ 2·108)和m(1 ≤ m ≤ 20)。第i行包含两个数字ai和bi(1 ≤ ai ≤ 108, 1 ≤ bi ≤ 10).。所有输入的数字都是整数。

输出

输出只有一行——问题的答案。