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.

题目描述

小A在跳舞机上玩游戏，游戏中有N个“箭头”，箭头依次标号为1到N，并且的相应的分数S[1..N]。踏中第i号箭头你将获得相应的分数S[i]，否则将被扣除相应的分数。

如果累积踩中箭头T次，将获得combo奖励，如果是在第i个箭头时获得combo奖励，将会得到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， 其中4 和 10时combo奖励。

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

输入格式

第一行两个整数N和T。

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

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

输出格式

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

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

39

提示

【样例解释】

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

【数据范围】

对于20%的数据0≤N,T≤100；

对于100%的数据0≤N,T≤5000；

S和B各有N个数，所有分数为[0，10000]之间的整数。