首页 > 试题广场 >

Maximize The Beautiful Value

[编程题]Maximize The Beautiful Value

热度指数：10 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

Today HH finds a non-decreasing sequence(a₁,a₂....a_n,a_i≤a_i+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 a_i to a_j 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≤10⁵,1≤k<n)，the length of the sequence ,the least steps you need to move. 
 The second line contains n integers a₁,a₂…a_n(1≤a_i≤10⁸) - the sequence.

输出描述:

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

示例1

输入

输出

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]