题目描述

校园科技节前，社团需要采购 $n$ 份基础材料。共有 $m$ 个供货点可以购买材料，第 $i$ 个供货点的单价为 $p_i$，最多能提供 $a_i$ 份。

社团可以从每个供货点购买不超过其上限的整数份材料。已知所有供货点的总供货量能够满足需求，请计算买够 $n$ 份材料所需的最小总费用。

输入格式

第一行包含两个整数 $n,m$，分别表示需要购买的材料份数和供货点数量。

接下来 $m$ 行，每行包含两个整数 $p_i,a_i$，表示第 $i$ 个供货点的单价和最多可购买数量。

输出格式

输出一行一个整数，表示满足需求的最小费用。

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

630

数据范围

对于 $100\%$ 的数据，$0\le n,a_i\le 2\times 10^6$，$0\le m\le 5000$，$0\le p_i\le 1000$。