# #P16B. Burglar and Matches

# Burglar and Matches

## Description

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

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 the only number — answer to the problem.

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

## Samples

```
7 3
5 10
2 5
3 6
```

```
62
```

```
3 3
1 3
2 2
3 1
```

```
7
```