题目描述

给定一个大小为 $n$ 的整数数组 $a$。初始时，数组所有元素均被涂为红色。

你需要执行以下操作：

• 选择恰好 $k$ 个元素并将其涂为蓝色。
• 在存在至少一个红色元素的情况下，选择任意一个与蓝色元素相邻的红色元素并将其涂为蓝色。

换句话说，操作一初始执行 $1$ 次，接下来反复执行 $n-k$ 次操作 $2$ 使得整个数组都为蓝色。

涂色成本定义为以下两部分之和：

• 初始选择的 $k$ 个元素之和。
• 最后一个被涂色的元素的值。

你的任务是计算给定数组可能达到的最大涂色成本。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 代表测试数据组数，接下来每一组数据：

• 第一行输入输入两个空格隔开的整数分别代表 $n,k$。
• 接下来一行输入 $n$ 个正整数分别为 $a_1,a_2,\cdots,a_n$。

输出格式

对于每个测试用例，输出一个整数——该数组可能达到的最大涂色成本。

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

5
10
8

提示

样例 1 解释

• 第一组数据中，初始涂色第 $2$ 个元素，随后按顺序涂色第 $1$、$3$ 个元素。涂色成本为 $2 + 3 = 5$。

• 第二组数据中，初始涂色第 $1$ 和第 $5$ 个元素，随后按顺序涂色第 $2$、$4$、$3$ 个元素。涂色成本为 $4 + 3 + 3 = 10$。

• 第三组数据中，初始涂色第 $2$、$3$、$4$ 个元素，随后涂色第 $1$ 个元素。涂色成本为 $2 + 2 + 2 + 2 = 8$。

数据范围

对于 $100\%$ 的数据，$1\le t\le 10^3$，$2\leq n\leq 10^5$，$1\leq k<n$。保证所有数据的 $n$ 之和不超过 $10^5$。

• 子任务 $1$（$30$ 分）：$k=1$。
• 子任务 $2$（$30$ 分）：$n\leq 1000$。
• 子任务 $3$（$40$ 分）：没有特殊限制。