217. 取數字-簡單

取數字-簡單

給定一個正整數陣列$a_1,a_2...a_N$，若要從陣列中取出一些數字，且任兩數距離不小於$K$，求數字總合最大為多少？意即：對於$i, j$，若要同時取出$a_i$與 $a_j$，必須滿足$|i-j| \geq K$。特別地，若$K=1$表示完全沒有限制，$K=2$表 示兩數不能相鄰。

輸入說明

第一行為一個正整數$T$，$T \leq 10$，表示共有$T$筆測資。

每筆測資第一行為兩個正整數$N$、$K$，$1 \leq K \leq N \leq 1000$。

每筆測資第二行為$N$個正整數$a_i$，表示陣列中的$N$個元素，$1 \leq a_i \leq 1000$。

輸出說明

對於每筆測資，輸出取出的數字總合最大值。

範例輸入

2 4 2 1 2 3 4 4 3 1 3 4 2

範例輸出

6 4

測資說明

• 第一、第二筆測資保證$k=2$
• 第三、第四筆測資沒有這個限制

Judge Setting

run-time limit: 50 ms
memory limit: 131072 byte
測資數量: 0