유유를 가공하는 회사에서 업자별 리터당 가격과 가진 양이 주어질 때 우유를 가장싸게 구입하고자 한다. 이를 해결하는 문제이다.

입력 형식

• 사야 할 우유 양 N( 1 <= N <= 2,000,000)과
• 우유를 팔고자 하는 업자수 M(0 <= M <= 5,000)

다음 M 줄에는 각 업자 당 2 개의 정수값이 주어진다.

• 첫 번째 수는 1 리터당 가격 P ( 0 <= P <= 1,000)
• 이 업자가 가진 우유양 A ( 0 <= A <= 2,000,000)

출력 형식

입출력 예

입력 

100  5
5  20
9  40
3  10
8  80
6  30

출력

630

출처:usaco