NAPTIME - Naptime

题意翻译

在某个星球上,一天由 $n$ 小时构成。我们称 $0 \sim 1$ 点为第一个小时,$1 \sim 2$ 点为第二个小时,以此类推。在第 $i$ 个小时睡觉能恢复 $U_i$ 点体力。在这座星球上住着一头牛,它每天要休息 $B$ 个小时,它休息的这 $B$ 个小时可以不连续,可以分成若干段,但是在每一段的第一个小时不能恢复体力,从第二个小时开始才可以恢复体力。 为了身体健康,这头牛希望遵循生物钟,每天采用相同的睡觉计划。另外,因为时间是连续的,每天的第 $n$ 个小时与下一天的第一个小时是相连的,这头牛只需要在 $n$ 个小时内休息 $B$ 个小时就够了。 请你给这头牛安排一个任务计划,使得它每天恢复的体力最多。 输入格式: 第一行一个整数 $T$ 表示有 $T$ 组测试数据 对于每一组测试数据,第一行为两个整数 $n$ 与 $B$,接下来 $n$ 行每行一个整数 $U_i$。$2 \le B < N \le 3830 , 0 \le Ui \le 2 \times 10^5$。 输出格式: 对于每组输入数据,对应一行输出一个整数,表示答案。(注意:两组输出之间没有空行)

题目描述

Goneril is a very sleep-deprived cow. Her day is partitioned into N (3 <= N <= 3,830) equal time periods but she can spend only B (2 <= B < N) not necessarily contiguous periods in bed. Due to her bovine hormone levels, each period has its own utility U\_i (0 <= U\_i <= 200,000), which is the amount of rest derived from sleeping during that period. These utility values are fixed and are independent of what Goneril chooses to do, including when she decides to be in bed. With the help of her alarm clock, she can choose exactly which periods to spend in bed and which periods to spend doing more critical items such as writing papers or watching baseball. However, she can only get in or out of bed on the boundaries of a period. She wants to choose her sleeping periods to maximize the sum of the utilities over the periods during which she is in bed. Unfortunately, every time she climbs in bed, she has to spend the first period falling asleep and gets no sleep utility from that period. The periods wrap around in a circle; if Goneril spends both periods N and 1 in bed, then she does get sleep utility out of period 1. What is the maximum total sleep utility Goneril can achieve?

输入输出格式

输入格式


_t_ – the number of test cases, then _t_ test cases follow. Each test case takes the following form: Two space-separated integers: _N_ and _B_, then _N_ lines follows Each line contains a single integer, _U\_i_, between 0 and 200,000 inclusive

输出格式


For each test case output a single integer, the maximum total sleep utility Goneril can achieve.

输入输出样例

输入样例 #1

1
5 3
2
0
3
1
4

输出样例 #1

6

Input/Output details:
The day is divided into 5 periods, with utilities 2, 0, 3, 1, 4 in that 
order. Goneril must pick 3 periods.

Goneril can get total utility 6 by being in bed during periods 4,
5, and 1, with utilities 0 [getting to sleep], 4, and 2
respectively.