Thu mua sữa bò

Một nhà máy chế biến sữa cần mua mỗi ngày \(N\) lít sữa từ \(M\) nông dân.
Mỗi nông dân \(i\) bán sữa với giá \(P_i\) đồng cho mỗi lít và có thể cung cấp tối đa \(A_i\) lít.

Hãy tìm cách mua sữa sao cho tổng số tiền bỏ ra là ít nhất, đồng thời tổng lượng sữa mua về không nhỏ hơn \(N\).
Đảm bảo rằng tổng lượng sữa mà các nông dân có thể cung cấp luôn đủ để đáp ứng nhu cầu \(N\).

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(0 \le N \le 2 \cdot 10^6\), \(0 \le M \le 5000\)).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(P_i\) và \(A_i\) (\(0 \le P_i \le 1000\), \(0 \le A_i \le 2 \cdot 10^6\)).

Output

In ra số tiền nhỏ nhất cần thiết để mua đủ \(N\) lít sữa.

Input

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

Output

630