#209. 购买贺年卡 普及−

时间限制:1000 ms 内存限制:128 MiB 输入文件:Cards.in 输出文件:Cards.out
题目类型:传统 评测方式:文本比较
上传者: root

注意

本题采用文件输入输出。

输入文件为 Cards.in, 输出文件为Cards.out

题目描述

新年快到了,笑笑打算给他的好朋友们发贺年卡,而且他已经选好了自己要购买的贺卡的样式。俗话说得好,货比三家,笑笑来到商店,看了各个商铺这种贺卡的价钱。不仅如此,笑笑还记住了每个商铺的存货量。
已知笑笑打算购买 张贺卡,问他最少花多少钱

输入格式

从文件 Cards.in 中读入数据。

第一行两个整数 。其中 表示要购买的贺卡的数量, 表示商铺的个数。

以下 行,每行两个整数,分别表示该商铺这种贺卡的单价和存货量。

输出格式

输出到文件 Cards.out 中。

仅一个数,表示笑笑花的最少钱数。

样例

样例输入

10 4
4 3
6 2
8 10
3 6

样例输出

36

数据范围与提示

样例解释:

先将最后一家买空(3元*6=18元)

再将第一家买空(4元*3=12元)

再从第二家买一张(6元*1=6元)

刚好十张,总价格36元

保证结果在长整型以内且总存货量不少于m,保证有且只有一个最优解

0<m,n<=1000