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

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

请你计算J最多可以拿到到多少金币。

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

每个测试文件包含 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 。

样例组 输入#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