問題文
高桥正在和他的朋友玩某个游戏。
在这个游戏中,玩家的目标是购买建筑物,扩建和翻新它们,并赚取尽可能多的钱。
高桥目前 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 的价格是 10 因此,延期花费的总金额为 10 。此外,扩建后的建筑 1 的价格是 13 。
- 建物 1 将得到扩展。当前建筑 1 的价格是 13 因此,延期花费的总金额为 23 。此外,扩建后的建筑 1 的价格是 16 。
- 建物 2 将得到扩展。当前建筑 2 的价格是 12 因此,延期花费的总金额为 35 。此外,扩建后的建筑 2 的价格是 16 。
- 建物 3 将得到扩展。当前建筑 3 的价格是 15 因此,延期花费的总金额为 50 。此外,扩建后的建筑 3 的价格是 20 。
通过这样做,4 扩建建筑物的费用 50 。 它将被扩展
入力例2
8 4 1 1 10 1 100 1 1000 1
出力例2
36
建物 1 在 8 倍。