始终递增

时间限制：2s
空间限制：1024MB

题目描述

需要预先确定一个长度为 $N$ 的正整数序列 $A$。随后依次执行 $Q$ 次操作，第 $q$ 次把 $x_q$ 加到 $A_{i_q}$。要求在初始状态和每次操作后始终满足

求初始序列元素和的最小可能值。

输入格式

N Q
i_1 x_1
i_2 x_2
...
i_Q x_Q

输出格式

输出最小初始元素和。

样例输入 1

4 2
1 2
2 3

样例输出 1

22

样例输入 2

4 2
2 3
1 2

样例输出 2

16

数据范围

• $2\le N\le2\times10^5$；
• $1\le Q\le2\times10^5$；
• $1\le i_q\le N$；
• $1\le x_q\le10^5$。