题目描述

Yuzu 又在商店街购买糖果。

总共有 $n$ 个商店在街上排成了一排。第 $i$ 个商店售卖一种美味度为 $a_i$ 的糖果。Yuzu 想让买到的糖果的美味度之和尽可能大，但是 Akari 和 Aoi 觉得 Yuzu 吃糖吃太多了，给 Yuzu 了以下限制：

• 只能在每个商店买最多一颗糖果；
• 不能在连续的 $k+1$ 个商店里购买糖果。

例如：假设 $n=5,k=2$，那么 Yuzu 可以在 $[1,3,5]$ 商店各买一颗糖果，也可以在 $[1,2,4,5]$ 商店各买一颗糖果，但是不允许在 $[2,3,4]$ 商店各买一颗糖果。

Yuzu 想知道，在受到限制的情况下，她能够购买的糖果的美味度之和的最大值。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行两个正整数 $n,k$；
• 接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 个商店售卖的糖果的美味度。

输出格式

对于每组数据，输出一个整数，代表 Yuzu 能够购买的糖果的美味度之和的最大值。

2
5 2
9 9 9 1 1
6 3
1 1 4 5 1 4

20
14

数据范围

• 对于 $30\%$ 的数据，$T \le 5$，$n \le 10^3$；
• 对于 $60\%$ 的数据，$T \le 5$，$n \le 10^5$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^6$，$1 \le n,\sum n \le 10^6$，$1 \le k \le n$，$0 \le a_i \le 10^9$。