跳舞

题目描述

小明今天得到一个跳舞毯游戏程序 Dance。游戏每次连续出 $N$ 个移动的“箭头”，箭头依次标号为 $1$ 到 $N$，并且的相应的分数 $S(1,2,\dots,n)$。如果你能“踏中”第 $i$ 号箭头，你将获得相应的分数 $S_i$；否则将被扣除相应的分数。

另外，游戏还有一个累计奖励机制：如果踏准次数累计达到 $T$，并且是在踏中第 $i$ 个箭头达到的，则将得到 $B_i$ 的奖励分数,累计也将清零，重新开始。

例如：$N＝6,T=3$，相应的 $S$ 和 $B$ 分别为 $\{1,2,3,4,5,6\}$ 和 $\{0,0,4,7,9,10\}$，如果小明踏中所有箭头，则得分为：$(1+2+3+4)+(4+5+6+10)＝35$。

小明是个 Dance 高手，可以踏中他想踏中的任意一个箭头。但他发现，根据给定的 $N,T,S,B$，踏中所有的箭头不一定能得最高分，小明很想知道最高能得多少分，你能帮助小明计算一下最多可得多少分吗？

输入格式

第一行两个整数 $N$ 和 $T$。

第二行 $N$ 个整数 $s_i$，为 $S$ 的相应分数。

第三行也有N个整数 $b_i$，为 $B$ 的相应分数。

输出格式

一个整数，可得到的最高分数。

样例 #1

样例输入 #1

6 3
1 2 3 4 5 6
1 1 1 20 1 1

样例输出 #1

39

提示

【样例解释】

跳过第一个，扣 $1$ 分，连踩 $3$ 个，得 $9$ 分，并获得附加分 $20$ 分，之后再连踩 $2$个，共 $39$ 分。

【数据范围】

对于 $20\%$ 的数据 $0\le N,T\le100$；

对于 $100\%$的数据 $0\le N,T\le5000$；

$S$ 和 $B$ 集合各有 $N$ 个数，保证对于任意一个 $s_i$ 和 $b_i$，有 $1\le s_i,b_i \le1000$。