题目背景

翻译自 BalkanOI 2018 Day1 T2「Homecoming」；由于洛谷远慢于 loj，因此将时间限制从 300ms 调整至 500ms。

题目描述

有 $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, \cdots, (i+K-1) \bmod N$ 的课本。$K$ 为给定的常数。
你的目的是赚钱而非 pass 所有课程。请求出你最多能赚多少美刀。

交互过程

本题只支持 C++ 语言使用函数交互测评。选手代码不需要也不能包含 homecoming.h，也不需要实现 main 函数。

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

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

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

样例

调用

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$

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