小苯的区间删除

题号：NC290356
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个由 $n$ 个整数组成的数组 $\{a_1, a_2, \dots, a_n\}$ ，他想要使得数组中的元素和最大。为此，小苯可以进行任意次以下操作（也可以不操作）：
$\hspace{23pt}\bullet\,$ 选择一个长度不超过 $k$ 的区间 $[l, r]\left(1 \leqq l \leqq r \leqq n;\ r-l+1 \leqq k\right)$ ，将 $a_l, a_{l+1},...,a_r$ 这段元素删除，并将其余元素按照原有顺序前后拼接起来。换句话说，操作后数组变为： $a_1, a_2,\dots,a_{l-1}, a_{r+1},\dots,a_n$ 。
$\hspace{15pt}$ 小苯想知道，在可以进行任意次上述操作的前提下，数组中的元素和最大可以变为多少。特别地，空数组的总和视为 $0$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入两个正整数  代表数组中的元素个数、操作的区间的长度上限。 
第二行输入  个整数  代表数组中的元素。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行。输出一个整数代表操作后数组的最大总和。

示例1

输入

复制

2
5 2
1 2 -2 -3 4
4 4
1 1 1 1

输出

复制

7
4

说明

对于第一组测试数据，删除区间  后，数组变为 ，总和为 。我们可以证明，这是操作能得到的最大总和。
对于第二组测试数据，数组中所有元素均为 ，因此不操作就是最优的。