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 翻译