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
# ip
assistant
#Here is Python program to find out the maximum amount of matches that a burglar can carry away.
= open("testdata.txt", "r")

# def input():
# 	return ip.readline().strip()

n, m = map(int, input().split())
cont = [0]*m 

for i in range(m):
	boxes, matches = map(int, input().split())
	cont[i] = [matches, boxes]

cont.sort(reverse=True)
count = 0 

for match, box in cont:
	x = min(n, box)
	count += match*x
	n -= x
	if n==0:
		break

print(count)