Solution - 1733A. Consecutive Sum

 Solution - 1733A. Consecutive Sum  

A. Consecutive Sum

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

• Choose two indices i$i$ and j$j$, in which imodk=jmodk$imodk=jmodk$ (1≤i<j≤n$1\le i<j\le n$).
• Swap ai$a_i$ and aj$a_j$.

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

Here xmody$xmody$ denotes the remainder from dividing x$x$ by y$y$.

Input

The first line contains one integer t$t$ (1≤t≤600$1\le t\le 600$) — the number of test cases.

Each test case consists of two lines.

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

The second line of each test case contains n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai≤109$0\le a_i\le {10}^9$)  — 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

11
7
15
10
2999999997

Note

In the first test case, we can get a score of 11$11$ if we select a1,a2$a_1,a_2$ without performing any operations.

In the third test case, we can get a score of 15$15$ if we first swap a1$a_1$ with a4$a_4$ and then select a3,a4,a5$a_3,a_4,a_5$.

→ Source

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long k, n, s, t, x, a[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(cin >> t; t--;)
    {
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
        {
            cin >> x;
            a[i % k] = max(a[i % k], x);
        }
        s = 0;
        for(int i = 0; i < k; i++)s += a[i];
        cout << s << endl;
        fill(a, a + k, 0);
    }
}