题目描述

新年快到了，小蓝打算给她的好朋友们发贺年卡，而且她已经选好了自己要购买的贺卡样式。

俗话说得好，货比三家。小蓝来到商店，查看了各个商铺这种贺卡的价钱，并记住了每个商铺的存货量。

已知小蓝打算购买 $m$ 张贺卡，请问她最少需要花多少钱。

输入格式

第一行输入两个整数 $m,n$，其中 $m$ 表示要购买的贺卡数量，$n$ 表示商铺个数。

接下来 $n$ 行，每行两个整数，分别表示该商铺这种贺卡的单价和存货量。

输出格式

输出一个整数，表示小蓝需要花费的最少钱数。

样例

10 4
4 3
2 5
5 4
3 6

25

样例解释

优先购买价格较低的贺卡：先用单价 $2$ 购买 $5$ 张，再用单价 $3$ 购买 $5$ 张，共花费 $2\times5+3\times5=25$ 元。

数据范围

$0 < m,n \le 1000$，每个商铺贺卡单价在 $1\sim100$ 之间，数量在 $1\sim1000$ 之间。输入保证商铺的总存货量不少于 $m$。

来源

贪心 / 容器 / 结构体