3138: 可达鸭今天什么都吃

可达鸭的好朋友晴女士有 $n$ 只可爱的小可达鸭，小鸭们的重量为 $a_1,a_2,a_3,..,a_n$ 。现在晴女士出于某些阴暗的目的，想把这些小鸭放入 $k$ 个筐 $S_1, S_2, S_3,...,S_k$ 中，为了让生产周black鸭的机器正常运行，要求：

- 每只小鸭都必须被放入筐中。
- 每个筐中都至少有一只小鸭。
- 编号相邻的小鸭不可以放在一个筐内。（不然相邻的小鸭就会打架影响肉质）

现在我们将第 $i$ 个筐 $S_i$ 小鸭编号中最小的编号记为 $p_i$ ，求如何放置小鸭才可以使 $\sum\limits_{i=1}^ka_{p_i}$ 的值最大。

第一行输入一个整数 $T$，代表 $T$ 个测试数据。
$(30\%$ 数据 $T=1$ ， $60\%$ 数据 $1 \leq T\leq 10$ ，$100\%$ 数据 $1 \leq T\leq 5 \times 10^3)$
对于每个测试数据：
第一行包括 $n$ 和 $k$ 两个整数 $(2\leq k\leq n\leq 10^6)$
第二行包括 $n$ 个用空格分隔的数据 $a_1, a_2, a_3,...,a_n$ $(0\leq a_i \leq 10^9)$
数据保证 $\sum n \leq 10^6$

对于每个测试数据，输出一个数字，代表合法方案中最大的 $\sum\limits_{i=1}^ka_{p_i}$ 值

3
5 3
5 2 6 8 2 
7 4
10 1 6 3 6 7 7 
8 4
10000 1 20 500 7000 60 8 10

15
25
17501