题目描述

开心乳制品制作公司从奶农们手里采购牛奶，并将其加以包装，卖给零售店。

这样我们就可以从零售店买牛奶喝了。

由于牛奶加工这一行业的利润实在是很低，为了尽可能的降低成本，就需要尽可能的以低价向奶农购进牛奶。

开心乳制品制作公司拥有非常出色的营销部门，并且确切地知道他们每天需要多少牛奶进行包装卖给客户。

公司与多个奶农签有牛奶订购合同，不同奶农提供的牛奶的价格可能不同。

由于，奶牛的产奶量十分固定，所以奶农们也可以确定他们每天可以提供多少牛奶。

每天，公司可以从奶农那里购进任意整数单位的牛奶，当然，购进数量不能超过奶农所能提供牛奶的最大量。

现在给定：

• 开心乳制品制作公司的牛奶每日需求量
• 每位奶农所提供的牛奶的单位价格
• 每位奶农所能提供的牛奶的最大量

请你计算，开心乳制品制作公司能够满足其日常牛奶需求的最小花费是多少。

所有奶农能够提供的牛奶总量一定大于该公司的牛奶需求量。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示牛奶的日需求量和奶农的数量。

接下来 $M$ 行，每行包含两个整数 $P_i$ 和 $A_i$，表示一名奶农的牛奶单位价格以及所能提供牛奶量。

输出格式

输出一个整数，表示在能够满足日常牛奶需求情况下的最小花费。

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

630

提示

$0≤N≤2×10^6,$

$0≤M≤5000,$

$0≤P_i≤1000,$

$0≤A_i≤2×10^6$