该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

算协的积分挑战中有一列 $n$ 张卡片，第 $i$ 张卡片上的积分为正整数 $a_{i}$。给定参数 $k$，你的初始得分为 $0$。

只要当前卡片数量 $m$ 不小于 $k$，就必须选择并执行以下一种操作：

• 取走当前从左向右数第 $k$ 张卡片，将其积分加入得分；

• 取走当前从右向左数第 $k$ 张卡片，将其积分加入得分。

取走卡片后，其余卡片保持相对顺序，并按当前顺序重新编号。若两个位置指向同一张卡片，该次操作只取走这一张卡片并计分一次。当剩余卡片少于 $k$ 张时，操作结束。

请计算能够获得的最大总得分。

输入格式

第一行包含一个整数 $T$（$1\le T\le10^{4}$），表示测试数据组数。

对于每组测试数据，第一行包含两个整数 $n,k$（$1\le k\le n\le10^{5}$）；第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$（$1\le a_{i}\le10^{9}$）。同一行的相邻整数以一个半角空格分隔。

保证所有测试数据中 $n$ 的总和不超过 $10^{5}$。

输出格式

对于每组测试数据，输出一行一个整数，表示最大总得分。

4
4 2
1 2 3 4
4 4
3 4 1 2
1 1
1
6 3
1 4 8 2 6 3

9
3
1
19

样例解释

从左、从右的位置均根据每次操作前的当前序列计算。即使可以取走的两张卡片积分不同，也不能只凭当前积分大小断定最优操作。