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
Solve the task in PYTHON3.

=====
Can you provide 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.

import sys

def localmin():
    def recur(l, low, high, n):
        mid = (low + high) // 2
        while low != high:

            if l[mid] == 0 or l[mid - 1] == 0 or l[mid + 1] == 0:
                mid += 1
                continue
            # print(l[mid])
            if (mid > 0 and l[mid - 1] < l[mid]) or (mid < n - 1 and l[mid] > l[mid + 1]):
                low = mid + 1
                mid = (low + high) // 2
                # mid = (low + high) //2
            elif (mid < n - 1 and l[mid] < l[mid + 1]) or (mid > 0 and l[mid - 1] > l[mid]):
                high = mid
                mid = (low + high) // 2
        # print(l[low])
        return low + 1
        # mid = (low + high) // 2
        # if (mid == 0 or l[mid - 1] > l[mid]) and (mid == n - 1 or l[mid + 1] > l[mid]):
        #     return mid + 1
        # elif (mid > 0 and l[mid - 1] < l[mid]):
        #     return recur(l, low, mid, n)
        # return recur(l, mid + 1, high, n)

    num = int(input())
    l = [0] * num
    for i in range(1, num + 1):
        print('?', i, sep=' ')
        sys.stdout.flush()
        l[int(input()) - 1] = i
        if i == 101:
            break
    return '! ' + str(recur(l, 0, len(l) - 1, len(l) - 1))

# print(localmin())

def painting():
    num = int(input())
    l = input().split()
    pos = 0
    c = 0
    # pos1 = pos
    l1last = ''
    llast = ''
    while pos < num:
        if l[pos] != llast:
            llast = l[pos]
            pos1 = pos + 1
            c += 1
        while pos1 < num and l[pos1] == llast:
            pos1 += 1
        try:
            if pos1 - pos != 1 and l[pos1] != l1last:
                c += 1
                l1last = l[pos1 - 1]
        except:
            return c + 1
        pos = pos1
    return c

# print(painting())

def arena():
    case = int(input())
    for _ in range(case):
        num = int(input())
        l = sorted(list(map(int, input().split())))
        minn, *l = l
        for i, v in enumerate(l):
            if v > minn:
               ...