题目描述

沙雕学院想要采购一批狗屎为学员们补充营养，为了降低成本，沙雕学院的TomAnderson打算直接从废品回收站采购狗屎，自行加工。

TomAnderson从一些废品回收站手中采购狗屎，废品回收站们提出的的价格可能相同，且每天能提供的狗屎数量是一定的。每天TomAnderson可以从废品回收站手中采购到小于或者等于废品回收站最大产量的整数数量的狗屎。

给出TomAnderson每天对狗屎的需求量，还有每位废品回收站提供的狗屎单价和产量。计算采购足够数量的狗屎所需的最小花费。

每天所有废品回收站的总产量大于TomAnderson的需求量。

输入格式

第一行二个整数n,m，表示需要狗屎的总量，和提供狗屎的废品回收站个数。

接下来m行，每行两个整数p[i],a[i]，表示第i个废品回收站狗屎的单价，和废品回收站i一天最多能卖出的狗屎量。

输出格式

单独的一行包含单独的一个整数，表示沙雕学院拿到所需狗屎所要的最小费用

输入数据1

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

输出数据1

630

输入数据2

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

输出数据2

250

提示

【数据范围】 对于100%的数据： 0≤n，a[i]≤2×1000000，0≤m≤5000，0≤p[i]≤1000

原题传送门

点击进入