Description
题目描述
为了保证足够的利润，尽可能降低牛奶的采购成本是每一个生产厂家都要考虑的问题。由于品质不尽相同，不同奶农的牛奶的收购价格也不尽相同。厂家可以全部或者部分收购奶农的牛奶。给出厂家每日的牛奶需求量以及每户奶农可提供的牛奶量及单价，请你计算厂家所要付出收购费用的最小值。
注意:每天农民生产的牛奶的总数对快乐的牛奶制造者来说足够的.
输入格式
第 1 行:二个整数, S 和 N。S是厂家需要牛奶量，N(0<= N<=200000)是奶农的数目.
第 2 到 M+1 行:每行二个整数,Pi 和 Ai。Pi(0<= Pi<=1,000) 是奶农 i 牛奶的价格，Ai(0 <= Ai <= 2,000,000)是农民 i 一天牛奶的供应量。
输出格式
一个整数，表示厂家所要付出收购费用的最小值。
输入样例
100 5
5 20
9 40
3 10
8 80
6 30
输出样例
630