题目描述
1
输入格式
64
输出格式
【问题描述】
由于面粉产品利润很低，所以降低原材料小麦的收购价格就变得十分重要。帮助A公司找到最优的小麦采购方案。
A公司从一些农民手中采购小麦，并且每一位农民为这些工厂提供的价格是不同的。此外，每位农民每天能提供的小麦数量是一定的。每天A公司可以从农民手中采购到小于或者等于农民最大产量的整数数量的小麦。
给出A公司每天对小麦的需求量，还有每位农民提供的小麦单价和最高供应数量。计算采购满足需求的小麦所需的最小花费。
【输入形式】
第 1 行共二个数值:N,(0<=N<=2,000,000)是需要小麦的总数；M,(0<= M<=5,000)是提供小麦的农民个数。
第 2 到 M+1 行:每行二个整数:Pi 和 Ai。
Pi(0<= Pi<=1,000) 是农民 i 的小麦的单价。
Mi(0 <= Ai <= 2,000,000)是农民 i 一天能卖给A公司的小麦最大数量。
【输出形式】
单独的一行包含单独的一个整数，表示A公司拿到所需的小麦所需要的最小费用。
【样例输入】
100 5
5 20
9 40
3 10
8 80
【样例输出】
630
【样例说明】
【评分标准】