## 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.

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

input

output

Copy

## Consecutive Sum solution codeforces

11 7 15 10 2999999997

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.