A94237.烦人的游戏

你有两个整数数组 $a$ 和 $b$ ，长度均为 $n$ ，以及一个总回合数 $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$ 表示测试用例的数量。每个测试用例的描述随后给出。

每个测试用例的第一行包含两个整数 $n$ 和 $k$，表示数组的长度和回合总数。

每个测试用例的第二行包含 $n$ 个整数 $a_{1},a_{2},\cdots,a_{n}$，表示数组 $a$ 的元素。

每个测试用例的第三行包含 $n$ 个整数 $b_{1},b_{2},\cdots,b_{n}$，表示数组 $b$ 的元素。

对于每个测试用例，输出一个整数，表示在 $k$ 回合后，假设双方都以最优策略进行游戏的最终得分。

样例解释

对于第一个测试用例：

• 任何操作都不能改变数组 $a$ ，因为 $b$ 中的所有元素都是零。

• 最终数组的最大非空子数组和为 $3 + (-1) + 9 = 11$ 。

对于第二个测试用例，一种可能的最优操作序列是：

• Alice 将 $b_{3}=1$ 加到 $a_{3}$ 。数组 $a$ 变为 $[10, 10, 11, 10]$ 。

• Bob 将 $b_{1}=1$ 从 $a_{1}$ 减去。数组 $a$ 变为 $[9, 10, 11, 10]$ 。

• Alice 将 $b_{3}=1$ 加到 $a_{3}$ 。数组 $a$ 变为 $[9, 10, 12, 10]$ 。

• Bob 将 $b_{1}=1$ 从 $a_{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$ 。

数据范围

$1 \le t \le 10^{4}$

$1 \le n \le 2\times 10^{5}$ ， $1 \le k \le 2\times 10^{5}$

$-10^{9} \le a_{i} \le 10^{9}$

$0 \le b_{i} \le 10^{9}$

保证所有测试用例的 $n$ 之和不超过 $2\times 10^{5}$。