题目描述

翻译自 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$

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