题目描述

有 $N$ 个元件排成一行，第 $i$ 个元件的价值为 $a_i$。每天可以选择若干个互不相邻的元件进行加工，当天收益为这些元件价值之和。

接下来有 $D$ 次修改。第 $i$ 次将位置 $P_i$ 的价值改为 $X_i$。每次修改后，都按当前价值求一天可获得的最大收益。

请输出 $D$ 次修改后的最大收益之和。可以不选择任何元件。

输入格式

第一行包含两个整数 $N,D$。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

接下来 $D$ 行，每行包含两个整数 $P_i,X_i$。

输出格式

输出一个整数，表示每次修改后答案的总和。

3 2
1 2 3
2 10
1 -5

20

数据范围与提示

• $1 \le N,D \le 4\times10^4$
• $|a_i|,|X_i| \le 10^9$