题目描述

饮品店今天需要采购不少于 $n$ 升鲜奶。共有 $m$ 位供应商，第 $i$ 位供应商的单价为 $p_i$ 元，每天最多能供应 $a_i$ 升。

所有供应商的总供应量足够满足需求。请计算买够 $n$ 升鲜奶所需的最小费用。

输入格式

第一行包含两个整数 $n,m$，分别表示需求量和供应商数量。

接下来 $m$ 行，每行输入两个整数 $p_i,a_i$，表示单价和最大供应量。

输出格式

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

10 3
5 4
3 6
4 10

34

数据范围与提示

• $0\le n,a_i\le 2\times10^6$
• $0\le m\le 5000$
• $0\le p_i\le 1000$
• 且总供应量不少于 $n$