CF2158C.Annoying Game

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$，以及总操作轮数 $k$。

Alice 和 Bob 一起玩一个游戏，轮流对数组 $a$ 进行修改。Alice 先手。游戏共进行 $k$ 轮。

在每轮中，当前玩家必须选择一个索引 $i$（$1 \leq i \leq n$），并执行以下操作之一：

• 加法：将 $a_i$ 增加 $b_i$，即令 $a_i := a_i + b_i$；
• 减法：将 $a_i$ 减少 $b_i$，即令 $a_i := a_i - b_i$。

第 $k$ 轮结束后，最终得分定义为修改后数组 $a$ 的最大非空子数组和。Alice 的目标是最大化最终得分，而 Bob 的目标是最小化最终得分。

假设双方都采取最优策略，请你计算最终得分。

数组 $a$ 的最大非空子数组和定义为 $\max_{1 \leq i \leq j \leq n} S(i, j)$，其中 $S(i, j) = a_i + a_{i+1} + \cdots + a_j$。注意，不考虑空子数组。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）表示测试用例个数。

每个测试用例第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 2 \cdot 10^5$）——数组的长度和总的操作轮数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$0 \leq b_i \leq 10^9$），表示数组 $b$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

每个测试用例输出一行一个整数，表示在 $k$ 轮操作结束后，双方最优博弈下的最终得分。

对于第一个测试用例：

• 所有 $b$ 中的元素均为零，因此无论如何操作数组 $a$ 都不会变化。
• 最终数组的最大非空子数组和为 $3 + (-1) + 9 = 11$。

对于第二个测试用例，其中一种可能的最优操作顺序为：

• Alice 将 $b_3=1$ 加到 $a_3$ 上。数组 $a$ 变为 $[10, 10, 11, 10]$。
• Bob 从 $a_1$ 减去 $b_1=1$。数组 $a$ 变为 $[9, 10, 11, 10]$。
• Alice 再次将 $b_3=1$ 加到 $a_3$ 上。数组 $a$ 变为 $[9, 10, 12, 10]$。
• Bob 再次从 $a_1$ 减去 $b_1=1$。数组 $a$ 变为 $[8, 10, 12, 10]$。
• Alice 将 $b_4=1$ 加到 $a_4$ 上。数组 $a$ 变为 $[8, 10, 12, 11]$。
• 最终数组最大非空子数组和为 $8+10+12+11 = 41$。

对于第三个测试用例，其中一种可能的最优操作顺序为：

• Alice 将 $b_2=11$ 加到 $a_2$ 上。数组 $a$ 变为 $[2, 4, 3]$。
• 最终数组最大非空子数组和为 $2+4+3=9$。

对于第四个测试用例，其中一种可能的最优操作顺序为：

• Alice 将 $b_2=11$ 加到 $a_2$ 上。数组 $a$ 变为 $[2, 4, 3]$。
• Bob 将 $b_2=11$ 从 $a_2$ 中减去。数组 $a$ 变为 $[2, -7, 3]$。
• 最终数组最大非空子数组和为 $3$。

由 ChatGPT 5 翻译