You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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

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

子任务编号	附加限制	分值
$1$	$1\le S_N\le 500$	$13$
$2$	$1\le S_N\le 5000$	$18$
$3$	$1\le S_{NK}\le 2\times 10^6$	$31$
$4$	无附加限制	$38$