A - Always Increasing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ 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）として与えられ，その内容は A_{i_q} に x_q を加算するというものです．

あなたの目標は，A の初期状態を適切に定めることで，どの時点においても（つまり，初期状態および各操作の直後においても）以下の条件が成り立つようにすることです．

  • 0<A_1 < A_2 < \cdots < A_N が成り立つ．

この目標を達成するとき，A の初期状態における要素の総和として考えられる最小値を求めてください．

制約

  • 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
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられます．

N Q
i_1 x_1
\vdots
i_Q x_Q

出力

目標を達成するとき，A の初期状態における要素の総和として考えられる最小値を出力してください．

入力例 1

4 2
1 2
2 3

出力例 1

22

初期状態の A が A=(1,4,8,9) であったとします．このとき，

  • 1 回目の操作直後の A：A=(3,4,8,9)
  • 2 回目の操作直後の A：A=(3,7,8,9)

となり，どの時点においても A は条件を満たしていることが確かめられます．

この場合，A の初期状態における要素の総和は \displaystyle \sum_{i=1}^NA_i=1+4+8+9=22 です．

入力例 2

4 2
2 3
1 2

出力例 2

16

入力例 3

100000 1
1 100000

出力例 3

14999950000

Score : 300 points

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\ldots,A_N) of length N, and you will perform Q operations on it. For 1\leq q\leq Q, the q-th operation is given as positive integers i_q, x_q (where 1\leq i_q\leq N), and it adds x_q to A_{i_q}.

Your goal is to appropriately determine the initial state of A so that the following condition holds at any point in time (that is, in the initial state and immediately after each operation).

  • 0<A_1 < A_2 < \cdots < A_N holds.

When achieving this goal, find the minimum possible sum of elements in the initial state of A.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
i_1 x_1
\vdots
i_Q x_Q

Output

Output the minimum possible sum of elements in the initial state of A when achieving the goal.

Sample Input 1

4 2
1 2
2 3

Sample Output 1

22

Suppose the initial state of A is A=(1,4,8,9). Then,

  • A immediately after the 1-st operation: A=(3,4,8,9)
  • A immediately after the 2-nd operation: A=(3,7,8,9)

and it can be verified that A satisfies the condition at any point in time.

In this case, the sum of elements in the initial state of A is \displaystyle \sum_{i=1}^NA_i=1+4+8+9=22.

Sample Input 2

4 2
2 3
1 2

Sample Output 2

16

Sample Input 3

100000 1
1 100000

Sample Output 3

14999950000