给定两个整数数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$,总圈数 $$$k$$$。
Alice 和 Bob 通过轮流修改数组 $$$a$$$ 来玩游戏。爱丽丝先走。游戏持续 $$$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$$$ 的
的 树的 最大非空子数组总和 修改后的数组 $$$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 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_{n}$$$ ($$$0 \le b_i \le 10^9$$$) — 数组 $$$b$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - $$$k$$$ 回合后的最终分数,假设两个玩家都发挥最佳。
示例
输入复制
55 2000003 -1 9 -5 40 0 0 0 04 510 10 10 101 1 1 13 12 -7 31 11 33 22 -7 31 11 31 1-32
输出复制
114193-1
注意
对于第一个测试用例:
- 任何移动都无法更改数组 $$$a$$$,因为 $$$b$$$ 中的所有元素均为零。
- 此最终数组的最大非空子数组和为 $$$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 从 $$$a_2$$$ 中减去 $$$b_2=11$$$。数组 $$$a$$$ 变为 $$$[2, -7, 3]$$$。
- 此最终数组的最大非空子数组和为 $$$3$$$。