AT_arc210_a [ARC210A] Always Increasing

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

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ i_1 $ $ x_1 $ $ \vdots $ $ i_Q $ $ x_Q $

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

### Sample Explanation 1 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 $ . ### 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.