A2750 | 大盗杰瑞

时间限制：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$ 在单独的一行中输出答案。