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 code to find out the maximum amount of matches that a burglar can carry away?
assistant
#Here is Python code to find out the maximum amount of matches that a burglar can carry away.

#python3
import math

class BurglarAndMatches:
    @staticmethod
    def read_input():
        capacity_and_containers = input('').split()

        capacity = int(capacity_and_containers[0])
        num_containers = int(capacity_and_containers[1])

        profits, quantities = [], []
        for i in range(0, num_containers):
            a_and_b = input('').split()
            quantities.append(int(a_and_b[0]))
            profits.append(int(a_and_b[1]))

        return capacity, profits, quantities

    @staticmethod
    def break_items_into_log2_items(profits, weights, quantities):
        new_profits, new_weights, new_quantities = [0], [0], [0]
        for i in range(len(profits)):
            beta, k = 0, 1
            for j in range( math.floor(math.log2(quantities[i])) ):
                new_quantities.append(k)
                new_weights.append(k*weights[i])
                new_profits.append(k*profits[i])
                beta += k
                k *= 2
            remaining_quant = quantities[i] - beta
            new_quantities.append(remaining_quant)
            new_weights.append(remaining_quant*weights[i])
            new_profits.append(remaining_quant*profits[i])
        return new_profits, new_weights, new_quantities

    @staticmethod
    def run_dp():
        capacity, profits, quantities = BurglarAndMatches.read_input()
        weights = [1 for w in range(len(profits)+1) ]
        profits, weights, quantities = BurglarAndMatches.break_items_into_log2_items(profits, weights, quantities)

        num_items = len(profits)-1
        knapsack = [ [0 for j in range(capacity+1)] for i in range(num_items+1) ]

        for i in range(num_items+1):
            for w in range(capacity+1):
                if w == 0 or i == 0: knapsack[i][w] = 0
                elif weights[i] > w: knapsack[i][w] = knapsack[i-1][w]
                else:
                    knapsack[i][w] = max(knapsack[i-1][w], profits[i] + knapsack[i-1][w-weights[i]])

        print(knapsack[num_items][capacity])

    @staticmethod
  ...