#216574. [EGOI 2026] 饼干 / Biscuits

Aurora 和 Bianca 特别喜欢意大利杏仁饼干，今天，她们的爷爷烤了一大堆饼干（形成一个栈）。为了分这些饼干，她们发明了以下游戏。只要栈里还有饼干，她们就重复以下步骤：

• Aurora 选一个整数 。
• 接下来，Bianca 选一个整数 ，满足：
  • 剩下的饼干至少有 个，并且
  • 。
• 然后 Aurora 吃掉最顶上的 个饼干（如果 就不吃）。
• 最后，如果还有剩下的饼干，Bianca 会吃掉最顶上的那一块。

当然，两个女生都想吃得越多越好。栈里的每块饼干都有一个重量 。当所有饼干被吃完后，每个人的幸福度等于她在游戏中吃掉的所有饼干的重量总和。两个女生都知道如何最优地玩这个游戏——每个人总是会做出能让自己的最终幸福度最大化的选择。

因为这个游戏太好玩了，她们现在每天都要玩！在接下来的 天里，她们的爷爷每天都会烤一堆同样数量的饼干。为了让游戏更有趣，爷爷每天会改变其中一块饼干的重量，而其他饼干的重量保持不变。

对于初始的饼干堆，以及在每天进行改变之后，你需要计算出每天游戏结束时 Bianca 的幸福度。

输入的第一行包含两个整数 和 ，分别是饼干的数量和变更的次数。饼干从上到下编号为 到 。

第二行包含 个整数 ，即饼干的初始重量。

接下来的 行中，第 行包含两个整数 和 ，描述第 次变更：爷爷将第 块饼干的重量改为 。换句话说， 的值变成了 。

输出 个整数，即每天游戏结束后 Bianca 的幸福度。

样例输入 1

2 1
10 15
1 1

样例输出 1

10
1

样例输入 2

5 2
1 1 1 1 2
2 20
3 30

样例输出 2

3
4
24

样例输入 3

4 2
1 2 4 8
3 2
2 3

样例输出 3

7
4
4

样例输入 4

3 0
1 1 1

样例输出 4

1

样例输入 5

3 4
50 8 1
1 1
1 8
2 7
2 1

样例输出 5

8
1
8
8
8

样例解释

第一个样例。 第一天，饼干的重量分别是 和 。

• Aurora 选择 是最优的。然后，Bianca 选择 并吃掉最顶上的饼干。
• 在第二回合，Aurora 选择 。Bianca 唯一的选择是 。然后，Aurora 吃掉重量为 的饼干，游戏结束。

第二天，第 号饼干的重量变为 ，此时饼干的重量为 。

• Aurora 选择 是最优的。然后，Bianca 选择 。Aurora 吃掉最顶上的饼干，Bianca 吃掉剩下的一块。

游戏结束后，Bianca 的幸福度为 。

第二个样例。 初始时，从上到下的饼干重量为 。

• Aurora 选择 是最优的。Bianca 选择 。Aurora 吃掉第一块，Bianca 吃掉第二块。
• 下一回合，Aurora 选择 。Bianca 选择 。Aurora 吃掉接下来的两块，Bianca 吃掉最后一块。游戏结束时，Bianca 的总幸福度为 。

第一次变更后，重量变为 。

• 现在 Aurora 选择 是最优的。（如果她选其他值，Bianca 会选择 ，那么 Aurora 就吃不到中间那块大饼干了。）响应 Aurora 的选择，Bianca 选择 并吃掉第一块饼干。剩下的饼干重量为 。
• 第二回合，Aurora 选择 ，Bianca 选择 。Bianca 再次吃掉最顶上的饼干。之后，剩下的饼干重量为 。
• 第三回合，Aurora 选择 。Bianca 选择 。之后，Aurora 吃掉重量为 和 的饼干，最后 Bianca 吃掉最后一块重量为 的饼干。Bianca 吃掉的饼干总重量为 。

第二次变更后，重量变为 。 如果两个女生都以最优策略进行游戏，Bianca 会吃掉除重量为 的那块以外的所有饼干。

约束条件

• 。
• 。
• （是的，意大利杏仁饼干很轻！）。
• 且 。

评分方式

你的程序将在分成若干子任务的测试数据上进行测试。 要获得某个子任务的分数，你必须正确解出该子任务中所有的测试数据。

• 子任务 0 [ 分]: 样例。
• 子任务 1 [ 分]: 且 。
• 子任务 2 [ 分]: 。
• 子任务 3 [ 分]: 在任何时候，饼干重量 都是非递增的；换句话说，。
• 子任务 4 [ 分]: 。
• 子任务 5 [ 分]: 。
• 子任务 6 [ 分]: 。
• 子任务 7 [ 分]: 没有额外的约束条件。