Nhà hàng Pizza_Egg có một số nông dân chuyên cung cấp trứng sạch và mỗi người có một giá bán khác nhau. Mỗi người nông dân chỉ có một số lượng trứng nhất định mỗi ngày, nhà hàng có thể mua một số trứng từ mỗi người nông dân, ít hơn hoặc bằng số lượng trứng của mỗi người nông dân đó. Biết số lượng trứng mỗi ngày mà nhà hàng cần, giá mỗi quả trứng và số lượng trứng mà mỗi người nông dân có.

Yêu cầu: Hãy tính số tiền ít nhất mà nhà hàng cần để mua được số trứng đó. Giả thiết tổng số trứng của người nông dân đủ đáp ứng nhu cầu của nhà hàng.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, M~. ~N~ là số trứng mà nhà hàng cần mỗi ngày (~0 < N \le 10^9~), ~M~ là số người nông dân cung cấp trứng cho nhà hàng (~0 < M \le 10^5~).
• Dòng thứ ~i~ trong ~M~ dòng tiếp theo, chứa hai số nguyên ~A_i~ và ~B_i~ cách nhau một khoảng trắng. ~A_i~ (~0 < A_i \le 5000~) là giá một quả trứng của người nông dân ~i~; ~B_i~ (~0 < B_i \le 1000~) là số trứng tối đa mà một người nông dân có thể bán cho nhà hàng.

Output

• Ghi ra một số nguyên là số tiền nhỏ nhất mà nhà hàng cần để mua đủ trứng mỗi ngày.

Sample Input 1

50 5
5 30
10 40
3 10
8 80
7 30

Sample Output 1

250