题目描述

乳制品加工厂每天需要从多家奶农处采购牛奶。每位奶农的牛奶单价不同，且每天的供货量有限。工厂需要在满足每日需求的前提下，使得总花费尽可能低。

已知：

• 工厂每日需求量；
• 每位奶农的牛奶单价和可供货量。

请计算工厂每日采购牛奶的最低花费。

注意：所有奶农的总供货量一定能够满足工厂的需求。

输入格式

• 第一行：两个整数 $N$ 和 $M$。

  $N$（$0 \le N \le 2000000$）为工厂每日所需的牛奶量。

  $M$（$0 \le M \le 5000$）为可供选择的奶农数量。

• 接下来 $M$ 行，每行两个整数 $P_i$ 和 $A_i$：

  $P_i$（$0 \le P_i \le 1000$）为第 $i$ 位奶农的牛奶单价（分/单位）。

  $A_i$（$0 \le A_i \le 2000000$）为第 $i$ 位奶农每日可提供的牛奶量。

输出格式

一行一个整数，表示工厂每日采购牛奶的最低总花费。

样例

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

630

提示

按单价从低到高贪心采购即可。