AT_abc353_g.[ABC353G] Merchant Takahashi

在 AtCoder 王国中，有 $N$ 个城镇，分别为城镇 $1$、城镇 $2$、……、城镇 $N$。从城镇 $i$ 移动到城镇 $j$ 需要支付通行费 $C\times|i-j|$ 日元。

作为商人的高桥君，打算参加即将举办的 $M$ 场市场中的 $0$ 场或多场。

第 $i$ 场市场的信息由整数对 $(T_i, P_i)$ 表示，表示第 $i$ 场市场在城镇 $T_i$ 举办，若高桥君参加则可获得 $P_i$ 日元。

对于所有 $1\leq i < M$，第 $i$ 场市场结束后，第 $i+1$ 场市场才开始。高桥君移动所需的时间可以忽略不计。

高桥君一开始拥有 $10^{10^{100}}$ 日元，并且在城镇 $1$。请你通过合理选择参加的市场和移动路线，求出高桥君能够获得的最大利润。

更严格地说，若 $M$ 场市场结束后，高桥君的最终所持金额为 $10^{10^{100}}+X$，请你输出 $X$ 的最大值。

输入以如下格式从标准输入读入。

$N$ $C$ $M$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_M$ $P_M$

请输出答案。

限制条件

• $1\leq N\leq2\times10^5$
• $1\leq C\leq10^9$
• $1\leq M\leq2\times10^5$
• $1\leq T_i\leq N\ (1\leq i\leq M)$
• $1\leq P_i\leq10^{13}\ (1\leq i\leq M)$
• 输入均为整数

样例解释 1

例如，高桥君可以按如下方式行动，使所持金额增加 $49$ 日元。

• 移动到城镇 $5$。所持金额变为 $10^{10^{100}}-12$ 日元。
• 参加第 $1$ 场市场。所持金额变为 $10^{10^{100}}+18$ 日元。
• 移动到城镇 $4$。所持金额变为 $10^{10^{100}}+15$ 日元。
• 参加第 $3$ 场市场。所持金额变为 $10^{10^{100}}+40$ 日元。
• 移动到城镇 $2$。所持金额变为 $10^{10^{100}}+34$ 日元。
• 参加第 $4$ 场市场。所持金额变为 $10^{10^{100}}+49$ 日元。
  无法使所持金额达到 $10^{10^{100}}+50$ 日元或更高，因此输出 49。

样例解释 2

由于通行费过高，高桥君最优选择是不离开城镇 $1$。

样例解释 4

请注意，输出的值可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译