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
import java.util.*;

/**
 *
 *
 *  @author Mustafa Arinmis
 *  @since 05.11.2020
 * */

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        TreeMap<Integer, Integer> containers = new TreeMap<>(Collections.reverseOrder());

        int key, value;
        for(int i=0; i<m; i++) {
            value = input.nextInt();
            key = input.nextInt();

            if(containers.containsKey(key))
                containers.put(key , value + containers.get(key));
            else
                containers.put(key , value);
        }



        int maxMatch = 0;
        for(Map.Entry entry : containers.entrySet()){
            if(n > (Integer)entry.getValue()) {
                maxMatch += (Integer) entry.getKey() * (Integer) entry.getValue();
                n -= (Integer) entry.getValue();
            }
            else{
                maxMatch += n *  (Integer) entry.getKey();
                break;
            }
        }

        System.out.println(maxMatch);

    }
}

