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.