Maximize The Beautiful Value
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Today HH finds a non-decreasing sequence(a1,a2....an,ai≤ai+1), he thinks it's not beautiful so he wants to make it beautiful.
To make it, HH will choose exactly one number and move it forward at least k steps(i.e. you can move ai to aj if k≤i−j), and then he defines the beautiful value F(n) as 
HH asks you to calculate max(F(n))

输入描述:

 The first line contains an positive integer T(1≤T≤10), represents there are T test cases. 
 For each test case: 
 The first line contains two positive integers n,k(1≤n≤105,1≤k<n)，the length of the sequence ,the least steps you need to move. 
 The second line contains n integers a1,a2…an(1≤ai≤108) - the sequence.

输出描述:

For each test case, you should output the max F(n).
示例1

输入

复制 
3
5 3
1 1 3 4 5
5 2
1 1 3 4 5
5 1
1 1 3 4 5

输出

复制 
46
50
53

说明

In the first example, you can move the fifth number 4 for 3 steps and make the sequence become [4,1,1,3,5], then the beautiful value is 4×1+1×2+1×3+3×4+5×5=46.
You can also move the fifth number to make it become [1,5,1,3,4], the beautiful value is also 46.
In the second example, you can move the  fifth number 5 for 2 steps and make the sequence become [1,1,5,3,4]
In the second example, you can move the  second number 1 for 1 steps and then the sequence is still [1,1,3,4,5]

备注:

scanf is commended。