Consecutive Sum solution codeforces

You are given an array 𝑎a with 𝑛n integers. You can perform the following operation at most 𝑘k times:

  • Choose two indices 𝑖i and 𝑗j, in which 𝑖mod𝑘=𝑗mod𝑘imodk=jmodk (1𝑖<𝑗𝑛1≤i<j≤n).
  • Swap 𝑎𝑖ai and 𝑎𝑗aj.

After performing all operations, you have to select 𝑘k consecutive elements, and the sum of the 𝑘k elements becomes your score. Find the maximum score you can get.

Here 𝑥mod𝑦xmody denotes the remainder from dividing 𝑥x by 𝑦y.

Input

Consecutive Sum solution codeforces

The first line contains one integer 𝑡t (1𝑡6001≤t≤600) — the number of test cases.

Each test case consists of two lines.

The first line of each test case contains two integers 𝑛n and 𝑘k (1𝑘𝑛1001≤k≤n≤100) — the length of the array and the number in the statement above.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖1090≤ai≤109)  — the array itself.

Output

For each test case, print the maximum score you can get, one per line.

Example

input

Copy
5
3 2
5 6 0
1 1
7
5 3
7 0 4 0 4
4 2
2 7 3 4
3 3
1000000000 1000000000 999999997

output

Copy

Consecutive Sum solution codeforces

11
7
15
10
2999999997
Note

In the first test case, we can get a score of 1111 if we select 𝑎1,𝑎2a1,a2 without performing any operations.

In the third test case, we can get a score of 1515 if we first swap 𝑎1a1 with 𝑎4a4 and then select 𝑎3,𝑎4,𝑎5a3,a4,a5.

Solution – CLICK HERE

Leave a Comment

Your email address will not be published.