题目描述

翻译自 BalkanOI 2018 Day1 T2「Homecoming」

有 $N$ 门课程，编号 $0$ 到 $N-1$。pass 课程 $i$ 可获得 $A_i$ 美元。

有 $N$ 本教材，编号 $0$ 到 $N-1$。教材 $i$ 的价格为 $B_i$ 美元。

pass 课程 $i$ 需要购买编号为 $i, (i+1)\bmod N, (i+2)\bmod N, \ldots, (i+K-1)\bmod N$ 的教材。$K$ 为给定常数。

目标是赚钱（不是 pass 所有课程），求最多能赚多少美元。

交互过程
本题只支持 C++ 语言使用函数交互测评。其他语言可参考「输入与输出」一节进行交互。

选手程序应包含头文件 homecoming.h。

选手程序需要实现如下函数：

long long int solve(int N, int K, int *A, int *B);

在一次运行中这个函数可能会被调用多次。

输入与输出
输入的第一行为一个整数 $T$，表示数据组数。

接下来 $T$ 组数据，对于每组数据：

• 第一行两个整数 $N,K$
• 第二行 $N$ 个整数 $A_i$
• 第三行 $N$ 个整数 $B_i$

对于每组数据，输出一行一个整数表示这组数据的答案。

样例

调用

solve(3, 2,
[40, 80, 100],
[140, 0, 20])

的返回值为 $60$。

数据范围及限制
令所有对 solve 函数的调用中 $N$ 的总和为 $S_N$，$NK$ 的总和为 $S_{NK}$。那么：

• $1\le K\le N\le 2\times 10^6$
• $1\le S_N\le 2\times 10^6$
• $0\le A_i,B_i\le 10^9$

详细子任务及附加限制如下表所示。