Problem Statement

Serval has just found a Kaitenzushi buffet restaurant. Kaitenzushi means that there is a conveyor belt in the restaurant, delivering plates of sushi in front of the customer, Serval.

In this restaurant, each plate contains exactly $k$ pieces of sushi and the $i$-th plate has a deliciousness $d_i$. Serval will have a meal in this restaurant for $n$ minutes, and within the $n$ minutes, he must eat up all the pieces of sushi he took from the belt.

Denote the counter for uneaten taken pieces of sushi as $r$. Initially, $r=0$. In the $i$-th minute ($1\leq i\leq n$), only the $i$-th plate of sushi will be delivered in front of Serval, and he can do one of the following:

• Take the $i$-th plate of sushi (whose deliciousness is $d_i$) from the belt, and $r$ will be increased by $k$;
• Eat one uneaten piece of sushi that he took from the belt before, and $r$ will be decreased by $1$. Note that you can do this only if $r>0$;
• Or, do nothing, and $r$ will remain unchanged.

Note that after the $n$ minutes, the value of $r$ must be $0$.

Serval wants to maximize the sum of the deliciousnesses of all the plates he took. Help him find it out!

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1\leq k<n\leq 2\cdot 10^5$) — the number of minutes of the meal and the number of sushi pieces in each plate.

The second line contains $n$ integers $d_1, d_2, \ldots, d_n$ ($1\leq d_i\leq 10^9$) — the deliciousness of each plate.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, print a single integer — the maximum possible sum of the deliciousnesses of all the plates Serval took.

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

void solve()
{
   int n,k;
   cin >> n >> k; // 每一盘有k个寿司
   vector<int> arr(n+1);
   for(int i=1;i<=n;i++) cin >> arr[i];
   priority_queue<int,vector<int>,greater<int>> q;
   int ans = 0;
   int cur = 0; // 结束时的r值，也是当前可以用来吃寿司的时间
   // 逆向遍历，固定结束时的r值
   for(int i=n;i>=1;i--)
   {
        if(cur >= k) // 可以吃当前盘就直接吃
        {
            q.push(arr[i]);
            ans += arr[i];
            cur -= k;
            continue;
        }
        // 反悔贪心，否则看当前盘可否替换，如果当前盘美味度大于小根堆堆顶则替换。
        if(!q.empty() and q.top() < arr[i])
        {
            ans += (arr[i] - q.top());
            q.pop();
            q.push(arr[i]);
        }
        cur++; //遍历回上一分钟，可以用来吃寿司的时间++
   }
   cout << ans << endl;
}