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
def q
=====
Write me 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.
16b():
	n, m = tuple([int(num) for num in input().split()])
	as_ = []
	bs_ = []
	for _ in range(m):
		a, b = tuple([int(num) for num in input().split()])
		as_.append(a)
		bs_.append(b)
	argsorted = sorted(range(len(bs_)), key=bs_.__getitem__)
	argsorted.reverse()
	total = 0
	for i in range(len(argsorted)):
		if(n <= 0):
			break
		total += min(as_[argsorted[i]], n) * bs_[argsorted[i]]
		n -= as_[argsorted[i]]
	print(total)
q16b()

# def q16b():
# 	n, m = tuple([int(num) for num in input().split()])
# 	boxes = []
# 	for _ in range(m):
# 		a, b = tuple([int(num) for num in input().split()])
# 		boxes = boxes + [b for _ in range(a)]
# 	boxes.sort()
# 	boxes.reverse()
# 	print(sum(boxes[:n]))

# q16b()