[Login|Register]
Problems

Status

Rank

Problem 1253
Children's Day
Time Limit: 1000ms
Memory Limit: 65536kb
Description
"池塘边的榕树上,知了在声声叫着夏天
草丛边的秋千上,只有蝴蝶停在上面
黑板上老师的粉笔还在拼命叽叽喳喳写个不停
等待着下课等待着放学等待游戏的童年 "
在一年前赢得了小镇的最佳草坪比赛后,小W变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,小W希望能够再次夺冠。
然而,小W的草坪非常脏乱,因此,小W只能够让他的奶牛通过啃草来完成这项工作。小W有N(1 <= N <= 100,000)只排成一排的奶牛,编号为1...N。每只奶牛的效率是不同的,奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。
靠近的奶牛们很熟悉,因此,如果小W安排超过K只连续的奶牛,那么,这些奶牛就会罢工去开派对:)。因此,现在小W需要你的帮助,计算小W可以得到的最大效率,并且该方案中没有连续的超过K只奶牛。
Input
第1行一个数字T(T不超过20),表示Case数量。对每一个Case:
* 第1行:空格隔开的两个整数N和K;
* 后跟N行,每行有一个整数E_i,表示奶牛i的效率。
Output
每个case输出一行,表示可以得到的最大的效率值。
Sample Input
1
5 2
1
2
3
4
5
Sample Output
12
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.1ms with 1 query(s).