C1059 - 混合牛奶
题目描述
由于乳制品产业利润很低，所以降低原材料（牛奶）价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。
Marry 乳业从一些奶农手中采购牛奶，并且每一位奶农为乳制品加工企业提供的价格可能相同。此外，就像每头奶牛每天只能挤出固定数量的奶，每位奶农每天能提供的牛奶数量是一定的。每天 Marry 乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。
给出 Marry 乳业每天对牛奶的需求量，还有每位奶农提供的牛奶单价和产量。计算采购足够数量的牛奶所需的最小花费。
输入格式
第一行二个整数 $n,m$，表示需要牛奶的总量，和提供牛奶的农民个数。
接下来 $m$ 行，每行两个整数 $p_i,a_i$，表示第 $i$ 个农民牛奶的单价，和农民 $i$ 一天最多能卖出的牛奶量。
输出格式
单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用。
输入输出样例
| 输入样例 | 输出样例 |
|---|---|
| 100 5 5 20 9 40 3 10 8 80 6 30 |
630 |
数据范围与提示
100%的数据：$0 \le n,a_i \le 2 \times 10^6$，$0\le m \le 5000$，$0 \le p_i \le 1000$
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1059.in，输出文件名为：C1059.out