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