No tag edit access

B. Burglar and Matches

time limit per test

0.5 secondmemory limit per test

64 megabytesinput

standard inputoutput

standard outputA 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 *a*_{i} matchboxes, and each matchbox contains *b*_{i} 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·10^{8}) and integer *m* (1 ≤ *m* ≤ 20). The *i* + 1-th line contains a pair of numbers *a*_{i} and *b*_{i} (1 ≤ *a*_{i} ≤ 10^{8}, 1 ≤ *b*_{i} ≤ 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2018 16:36:38 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|