AT_arc210_a.[ARC210A] Always Increasing

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$，你需要对其进行 $Q$ 次操作。对于 $1 \leq q \leq Q$，第 $q$ 次操作给出正整数 $i_q, x_q$（其中 $1 \leq i_q \leq N$），表示将 $x_q$ 加到 $A_{i_q}$ 上。

你的目标是合理确定 $A$ 的初始状态，使得在任意时刻（即初始状态以及每次操作后）始终满足以下条件：

• 始终有 $0 < A_1 < A_2 < \cdots < A_N$。

在满足上述目标的前提下，求初始状态下 $A$ 的所有元素和的最小可能值。

输入从标准输入读入，格式如下：

$N\ Q$
$i_1\ x_1$
$\vdots$
$i_Q\ x_Q$

输出初始状态下 $A$ 的所有元素和的最小可能值。

样例解释 1

假设初始状态下 $A=(1,4,8,9)$，则：

• 第 $1$ 次操作后：$A=(3,4,8,9)$
• 第 $2$ 次操作后：$A=(3,7,8,9)$

可以验证在任意时刻 $A$ 均满足条件。

此时初始状态下 $A$ 的元素和为 $\sum_{i=1}^N A_i = 1+4+8+9=22$。

数据范围

• $2 \leq N \leq 2\times 10^5$
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq i_q \leq N$
• $1 \leq x_q \leq 10^5$
• 所有输入值均为整数。

由 ChatGPT 5 翻译