题目描述

一家超市正在进行“买一送一”促销活动。货架上共有 $n$ 件羊驼玩偶排成一列，从左向右第 $i$ 件羊驼玩偶的价格为 $a_i$。

活动规则如下：

当你支付原价购买第 $i$ 件羊驼玩偶时，可以任选一件位于其右侧的羊驼玩偶 $j$（即 $i < j \le n$）作为赠品免费获得。

这意味着你只需支付 $a_i$ 元，即可获得第 $i$ 件和第 $j$ 件两件羊驼玩偶。

现在你希望通过这种方式总共获得 $2k$ 件羊驼玩偶，请问最少需要花费多少钱？

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

接下来对于每个测试用例：

• 第一行包含两个整数 $n$ 和 $k$，分别表示货架上的羊驼玩偶数量和需要获得的羊驼玩偶总数的一半。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每件羊驼玩偶的价格。

输出格式

对于每组用例，输出一行一个整数，表示获得 $2k$ 件羊驼玩偶的最小开销。

样例输入 1

1
6 2
10 1 10 2 10 3

样例输出 1

3

说明

样例解释

购买价格为 $1$ 的第 $2$ 件商品，可以免费获得第 $3$ 件商品； 购买价格为 $2$ 的第 $4$ 件商品，可以免费获得第 $5$ 件商品。 总开销为：$1 + 2 = 3$。 共获得 $4$ 件商品，满足 $2k = 4$。

其它样例说明

• 样例 2：见选手目录下的 alpaca/alpaca2.in 与 alpaca/alpaca2.ans，该测试用例满足测试点 $1 \sim 4$ 的约束条件。
• 样例 3：见选手目录下的 alpaca/alpaca3.in 与 alpaca/alpaca3.ans，该测试用例满足测试点 $5 \sim 10$ 的约束条件。
• 样例 4：见选手目录下的 alpaca/alpaca4.in 与 alpaca/alpaca4.ans，该测试用例满足测试点 $11 \sim 14$ 的约束条件。
• 样例 5：见选手目录下的 alpaca/alpaca5.in 与 alpaca/alpaca5.ans，该测试用例满足测试点 $15 \sim 20$ 的约束条件。

数据范围

• $1 \le t \le 10$
• $2 \le n \le 2 \times 10^5$，$n$ 为偶数
• $1 \le k \le \frac{n}{2}$
• $1 \le a_i \le 10^9$

各测试点的附加限制如下表所示：

点击下载大样例