最甜的小情侣

Problem Description

小 E 决定在小 L 生日时送她一个项链，用来展现自己的诚心，这个项链将从一个已有的项链中提纯得到。 具体的，项链由 $n$ 个宝珠构成，每个宝珠有价值 $a_i$。 小 E 可以选择其中若干宝珠，目标是最大化得到的宝珠价值之和，但要满足不能选择连续的 $>3$ 个宝珠，注意项链是环形的，所以首尾交接处也要满足这个规则。 情报可能有误，所以有若干修改操作 x v，表示将 $a_x$ 修改为 $v$。 请在初始情况，以及每次修改后，回答小 L 能得到的宝珠最大价值和。

Input

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。 对于每组测试数据：

• 第一行两个正整数 $n, q$，表示项链长度和修改次数。
• 第二行 $n$ 个正整数，表示价值序列 $a_1, a_2,\dots, a_n$。
• 接下来 $q$ 行，每行两个正整数 $x,v$，表示一次修改操作。

Output

对于初始情况以及每次修改，输出一行一个整数，表示对应的答案。

Sample Input

1
5 3
1 2 3 4 5
1 5
5 1
3 1

Sample Output

12
14
12
11

Hint

对于所有数据，$1\leq T\leq 5, 4\leq n\leq 2\times 10^5, 1\leq q\leq 10^5$，$1\leq a_i, v\leq 10^9$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（8）