题目描述

你需要购买 $n$ 件物品，出售这种物品的店铺共有 $k$ 家。每家店铺的售卖单价和存货数量可能不相同，请你计算：买完 $n$ 件物品所需要的最小花费。

输入格式

第一行：输入两个整数 $n,k$，分别表示所需物品数量和店铺数量。

此后 $n$ 行：每行输入两个整数 $a,b$，分别表示该店铺售卖的物品单价以及该店铺的存货数量。

输出格式

一个整数，表示最小总花费。

样例

10 4
4 3
6 2
8 10
3 6

36

样例 $1$ 解释

要买 $10$ 件物品，有 $4$ 个店铺。可以分别从第 $1,2,4$ 号店铺中购买 $3,1,6$ 个物品，总花费 $36$ 元。

数据规模与约束

对于所有数据，$1≤n,k,a,b≤100$，保证所需的物品数量不超过所有店铺的存量总和。