问题文

高桥君正在和他的朋友们玩一个游戏。

在这个游戏中，玩家需要购买建筑物，进行扩建，并尽可能多地赚钱。

高桥君目前排名第二，他必须想办法赚更多的钱，超过排名第一的青木君。

高桥君计划通过获得称号“扩建王”，利用政府提供的援助金来取得胜利。基于多年的经验，他知道通过扩建 $K$ 次可以成为扩建王。

高桥君目前拥有 $N$ 座建筑物。建筑物从 $1$ 到 $N$ 编号，最初没有任何建筑物被扩建过。

对于建筑物 $i (1 ≦ i ≦ N)$，已知以下事实：

• 建筑物 $i$ 扩建之前的价格为 $A_i$。
• 要对建筑物 $i$ 进行一次扩建，需要花费与当前价格相等的费用。
• 建筑物 $i$ 的价格每次扩建都会上涨 $D_i$。

由于高桥君同时采取其他策略，他希望尽量减少扩建所需的总费用。

请你代替高桥君，计算出 $K$ 次扩建所需的最小总费用。

输入

输入以以下格式从标准输入中给出。

$K$ $N$ $A_1$ $D_1$ $A_2$ $D_2$ : $A_N$ $D_N$

• 第 $1$ 行为成为扩建王所需的扩建次数 $K (1 ≦ K ≦ 10^8)$。
• 第 $2$ 行为高桥君拥有的建筑物数量 $N (1 ≦ N ≦ 10^5)$。
• 第 $3$ 至第 $N+2$ 行描述每座建筑物的信息。其中第 $i+2$ 行包含整数 $A_i (1 ≦ A_i ≦10^3)$ 和整数 $D_i (1 ≦ D_i ≦10^3)$，由空格分隔。

部分分

本问题设置了部分分。

• 当解决满足 $K ≦ 300$ 和 $N ≦ 300$ 的数据集 $1$ 时，得到 $30$ 分的分数。
• 当解决满足 $K ≦ 5,000$ 和 $N ≦ 5,000$ 的数据集 $2$ 时，除了上述分数外还额外得到 $10$ 分。
• 当解决满足 $K ≦ 10^5$ 的数据集 $3$ 时，除了上述分数外还额外得到 $15$ 分。
• 当解决不满足以上任何条件的数据集 $4$ 时，除了上述分数外还额外得到 $45$ 分。

输出

请输出一个整数，表示 $K$ 次扩建所需的最小总费用。在末尾加上换行符。

输入示例1

4
3
10 3
12 4
15 5

输出示例1

50

例如，按照以下步骤进行扩建：

1. 对建筑物 $1$ 进行一次扩建。当前建筑物 $1$ 的价格为 $10$，所以总费用为 $10$。扩建后建筑物 $1$ 的价格变为 $13$。
2. 对建筑物 $1$ 进行一次扩建。当前建筑物 $1$ 的价格为 $13$，所以总费用为 $23$。扩建后建筑物 $1$ 的价格变为 $16$。
3. 对建筑物 $2$ 进行一次扩建。当前建筑物 $2$ 的价格为 $12$，所以总费用为 $35$。扩建后建筑物 $2$ 的价格变为 $16$。
4. 对建筑物 $3$ 进行一次扩建。当前建筑物 $3$ 的价格为 $15$，所以总费用为 $50$。扩建后建筑物 $3$ 的价格变为 $20$。

通过这样的扩建，可以将 $K$ 次扩建所需的费用降至 $50$。

输入示例2

8
4
1 1
10 1
100 1
1000 1

输出示例2

36

对建筑物 $1$ 进行 $8$ 次扩建。