← 返回题目列表

AtCoder · arc021_3

C. 扩展王高桥

中文机器翻译题面 查看原题

問題文

高桥正在和他的朋友玩某个游戏。

在这个游戏中,玩家的目标是购买建筑物,扩建和翻新它们,并赚取尽可能多的钱。

高桥目前 2 并且必须以某种方式赚到比第一青木君更多的钱。

高桥计划利用从政府获得的援助资金,获得“扩建王”的称号,该称号授予扩建建筑物次数最多的人。从多年的经验来看, K 众所周知,通过多次扩展即可成为扩展王。

高桥目前 N 拥有一栋建筑物。大楼内 它的编号最大为 1 假设一直下雨,直到 N 。最初,没有任何建筑物被扩建。 以下是关于

建物 i (1 ≦ i ≦ N) 的已知信息。

  • 建物 i 扩展前的价格为 A_i 。
  • 建物 i 在 1 扩建建筑物 需要等于 i 当前价格的成本。
  • 建物 i 的价格是1 每次展开时 增加 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 行中,给出了建筑物信息。其中 i 行是一个整数 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 行输出。还在输出末尾添加换行符。


入力例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 。

通过这样做,4 扩建建筑物的费用 50 。 它将被扩展


入力例2

8
4
1 1
10 1
100 1
1000 1

出力例2

36

建物 1 在 8 倍。