此题动态规划，题目题目时间限制：1000ms 内存限制：128MB

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

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

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

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

每个测试文件包含 T 个测试用例。

数据范围

1≤T≤1000 1≤N, K≤10 5

1≤A 1​,A i​≤10 9 ∨A i​=−1 (2≤i≤N) 题目保证对于所有的测试用例 N 的总和不超过 10 5 。 输入格式 每个测试文件格式如下：

T Testcase 1​

Testcase 2​

⋮ Testcase T​

对于每个 Testcase 格式如下：

N K A 1​A 2​A 3​⋯ A N​

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

样例组 输入#1 4 10 3 3 1 -1 4 30 -1 8 7 3 5 5 1 1 3 7 7 2 10 4 11 4 12 23 -1 55 8 20 7 39 29 4 8 13 -1 3 14 6 1 -1 -1 1 2 26 -1 7 6 -1 7 9 24 3 2 -1 -1 2 19 2 -1 7 1 输出#1 37 20 57 88 提示说明 样例 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 枚金币。