题目描述

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$，以及总回合数 $k$。 Alice 与 Bob 轮流对数组 $a$ 进行修改，Alice 先行。游戏恰好进行 $k$ 回合。

在某一回合，玩家必须选择一个下标 $i$（$1\le i\le n$），并对 $a_i$ 执行下列两种操作之一：

• 加法（Add）：将 $a_i$ 增加 $b_i$，即 $a_i := a_i + b_i$；
• 减法（Subtract）：将 $a_i$ 减少 $b_i$，即 $a_i := a_i - b_i$。

当第 $k$ 回合结束时，最终得分定义为修改后数组 $a$ 的 最大非空子数组和（即 $\max_{1\le l\le r\le n} \sum_{t=l}^r a_t$，不考虑空子数组）。Alice 的目标是 最大化 最终得分，而 Bob 的目标是 最小化 最终得分。假设双方均完美博弈，请问最终得分是多少？

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$）——测试用例数。接下来为 $t$ 个测试用例，每个测试用例包含三行：

• 第一行：两个整数 $n$ 和 $k$（$1\le n\le 2\cdot 10^5$，$1\le k\le 2\cdot 10^5$）；
• 第二行：$n$ 个整数 $a_1,a_2,\dots,a_n$，满足 $-10^9\le a_i\le 10^9$；
• 第三行：$n$ 个整数 $b_1,b_2,\dots,b_n$，满足 $0\le b_i\le 10^9$。

额外保证：所有测试用例中 $\sum n \le 2\cdot 10^5$。

输出格式

对每个测试用例，输出一行，包含一个整数——在双方最优对抗下，经过 $k$ 回合后的最终得分（即最大非空子数组和）。

样例输入

5
5 200000
3 -1 9 -5 4
0 0 0 0 0
4 5
10 10 10 10
1 1 1 1
3 1
2 -7 3
1 11 3
3 2
2 -7 3
1 11 3
1 1
-3
2

样例输出

11
41
9
3
-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$ 。