测试数据来自 system/1754

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　为奖励小朋友的优异表现，H老师打算购买 \(m\) 个奖品分发给他们。

　　商店提供了 \(n\) 种精美奖品，第 \(i\) 种奖品的价格为 \(p_i\) 元，数量有 \(c_i\) 个。

　　那么H老师最少要花费多少元钱呢？

【输入格式】

　　第 1 行：共二个数值：\(m\) 和 \(n\)。
　　第 2 到 \(n+1\) 行：每行二个整数：\(p_i\) 和 \(c_i\)，\(p_i\) 是第 \(i\) 中奖品的价格，\(c_i\) 表示该奖品的数量。

【输出格式】

　　一个整数，表示H老师最少的花费。

【输入输出样例】

　Input

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

　Output

630

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤5000\)，\(1 ≤ m,p_i,c_i ≤ 2000000\)。

【来源】

　　Mr.he