A22403.大盗杰瑞

时间限制：1000ms
内存限制：128MB

大盗杰瑞盯上了一栋有 $N$ 层楼的大厦，大厦的每一层都有 $A_i$ 个金币，杰瑞可以在拿走第 $i$ 层楼上的所有金币后，通过楼梯前往大厦的第 $i + 1$ 层；

不过有的楼层上可能会有安保人员 $(A_i = -1)$，杰瑞为了不被抓到，不能直接越过这些楼层，但是这栋大厦每 $K$ 层有一个电梯，即大厦的 $1,\ K + 1,\ 2K + 1,\ 3K + 1,\ \cdots, \ j \times K + 1\ (j \times K + 1 \le N)$ 层上都有一个电梯，杰瑞可以乘坐电梯前往同样拥有电梯的更高楼层（无论该层是否有安保）。

请你计算杰瑞最多可以偷窃到多少金币。

$\bf{题目保证大厦的第一层不会有安保，且杰瑞只能上楼不能下楼。}$

$\bf{每个测试文件包含\ T\ 个测试用例。}$

$\large{数据范围}$

• $1 \le T \le 1000$
• $1 \le N,\ K \le 10^5$
• $1 \le A_1, A_i \le 10^9 \vee A_i = -1 \ (2 \le i \le N)$
• 题目保证对于所有的测试用例 $N$ 的总和不超过 $10^5$。

每个测试文件格式如下：

$T$
$Testcase_1$
$Testcase_2$
$\vdots$
$Testcase_T$

对于每个 $Testcase$ 格式如下：

$N\ K$
$A_1\ A_2\ A_3\ \cdots\ A_N$

对于每个 $Testcase$ 在单独的一行中输出答案。

样例 $1$：
从 $1$ 楼出发拿到 $3$ 枚金币，乘坐电梯前往 $4$ 楼，拿到 $4$ 枚金币，再通过楼梯到达 $5$ 楼拿到 $30$ 枚金币，一共可以拿到 $3 + 4 + 30 = 37$ 枚金币。

样例 $2$：
没有任何楼层有安保人员，可以拿到所有 $1 + 3 + 7 + 7 + 2 = 20$ 枚金币。

样例 $3$：
从 $1$ 楼出发拿到 $11$ 枚金币，乘坐电梯前往 $9$ 楼，拿到 $7$ 枚金币，在通过楼梯到达 $10$ 楼拿到 $39$ 枚金币，一共可以拿到 $11 + 7 + 39 = 57$ 枚金币。