AT_arc021_3.[ARC021C] 増築王高橋君

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

在这个游戏中，玩家的目标是购买建筑物并对其进行扩建，以赚取尽可能多的钱。

目前高桥君排名第 $2$，他必须想办法赚到比首位的青木君更多的钱。

高桥君计划通过获得授予扩建次数最多者的称号“扩建王”，利用政府的补助金来取得胜利。凭借多年的经验，他知道只要再扩建 $K$ 次就能成为扩建王。

高桥君目前拥有 $N$ 栋建筑。每栋建筑编号为 $1$ 到 $N$。一开始，所有建筑都没有被扩建过。

对于第 $i$ 栋建筑（$1 \leq i \leq N$），已知以下信息：

• 第 $i$ 栋建筑扩建前的价格为 $A_i$。
• 对第 $i$ 栋建筑进行一次扩建，需要支付等于该建筑当前价格的费用。
• 每对第 $i$ 栋建筑扩建一次，其价格就会上升 $D_i$。

高桥君还在同时进行其他策略，因此他希望用于扩建的总花费尽可能少。

请你帮高桥君计算，完成 $K$ 次扩建所需的最小总费用。

输入通过标准输入给出，格式如下：

$K$
$N$
$A_1\ D_1$
$A_2\ D_2$
$\vdots$
$A_N\ D_N$

• 第 $1$ 行给出成为扩建王所需的扩建次数 $K$，满足 $1 \leq K \leq 10^8$。
• 第 $2$ 行给出高桥君拥有的建筑数量 $N$，满足 $1 \leq N \leq 10^5$。
• 接下来的 $N$ 行，每行包含两个整数 $A_i$（$1 \leq A_i \leq 10^3$）和 $D_i$（$1 \leq D_i \leq 10^3$），分别表示第 $i$ 栋建筑扩建前的价格和每次扩建后价格的增加量。

输出完成 $K$ 次扩建所需的最小总费用。输出应为一行，末尾带换行符。

部分分

本题设有部分分。

• 若能通过满足 $K \leq 300$ 且 $N \leq 300$ 的数据集 $1$，可得 $30$ 分。
• 若能通过满足 $K \leq 5,000$ 且 $N \leq 5,000$ 的数据集 $2$，可再得 $10$ 分。
• 若能通过满足 $K \leq 10^5$ 的数据集 $3$，可再得 $15$ 分。
• 若能通过无额外限制的数据集 $4$，可再得 $45$ 分。

样例解释 1

例如，可以按如下方式扩建：

1. 扩建第 $1$ 栋建筑。当前价格为 $10$，总花费为 $10$。扩建后价格变为 $13$。
2. 再次扩建第 $1$ 栋建筑。当前价格为 $13$，总花费为 $23$。扩建后价格变为 $16$。
3. 扩建第 $2$ 栋建筑。当前价格为 $12$，总花费为 $35$。扩建后价格变为 $16$。
4. 扩建第 $3$ 栋建筑。当前价格为 $15$，总花费为 $50$。扩建后价格变为 $20$。

如此，完成 $4$ 次扩建所需的总花费为 $50$。

样例解释 2

对第 $1$ 栋建筑扩建 $8$ 次。

由 ChatGPT 4.1 翻译