human
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.

Input

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

Output the only number — answer to the problem.

Examples

Input

7 3
5 10
2 5
3 6

Output

62

Input

3 3
1 3
2 2
3 1

Output

7
 ... What is a Python program to find out the maximum amount of matches that a burglar can carry away?
assistant
#Here is Python program to find out the maximum amount of matches that a burglar can carry away.

class A:

    def solve(self):
        [n, m] = [int(x) for x in input().split(" ")]
        flag = []
        for i in range(n):
            flag.append(input())

        if any([len(set(x)) != 1 for x in flag]):
            print("NO")
            return

        first_colors = [x[0] for x in flag]
        if any([x == y for x, y in zip(first_colors, first_colors[1:])]):
            print("NO")
            return

        print("YES")

class B:

    def solve(self):
        [n, m] = [int(x) for x in input().split(" ")]
        matches = []
        for i in range(m):
            matches.append([int(x) for x in input().split(" ")])

        matches = sorted(matches, key=lambda x: x[1], reverse=True)

        total_matches = 0

        for (nums, matchsticks) in matches:
            if nums < n:
                n -= nums
                total_matches += nums * matchsticks
            else:
                total_matches += n * matchsticks
                n = 0

        print(total_matches)

B().solve()