CF2268A.K Is Important

You are given an array $a$ consisting of $n$ positive integers, as well as an integer parameter $k$.

While the array has at least $k$ elements, you need to perform one of the following two types of operations on $a$:

• Remove $a_k$ and add its value to your score, or
• Remove $a_{m-k+1}$ and add its value to your score, where $m$ is the length of $a$ before this operation.

After removing an element, the remaining elements keep their relative order.

Your task is to determine the maximum possible score that can be obtained.

给你一个由 $n$ 个正整数组成的数组 $a$，以及一个整数参数 $k$。

只要数组中至少包含 $k$ 个元素，你就需要对 $a$ 执行以下两种操作之一：

• 删除 $a_k$，并将它的值加到你的得分中；或
• 删除 $a_{m-k+1}$，并将它的值加到你的得分中，其中 $m$ 是本次操作前数组 $a$ 的长度。

删除一个元素后，其余元素保持其相对顺序不变。

你的任务是确定所能获得的最大可能得分。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the length of $a$ and the parameter.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the elements of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^5$）—— 分别表示数组 $a$ 的长度和参数。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）—— 即数组 $a$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single integer — the maximum score that can be obtained.

对于每个测试用例，输出一个整数——所能获得的最高得分。

In the first test case, we can first remove $a_3 = 3$. The score becomes $3$, and the array becomes $[1, 2, 4]$. Then we remove $a_2 = 2$, so the score becomes $5$, and the array becomes $[1, 4]$. Finally, we remove $a_2 = 4$, and the score becomes $9$. Now the length of the array is less than $k=2$, so no more operations can be performed. It can be proven that the maximum score is $9$.

In the second test case, we can only perform one operation, either removing $a_1 = 3$ or $a_4 = 2$. Obviously, it is better to remove $a_1 = 3$ to get a score of $3$.

在第一个测试用例中，我们首先移除 $a_3 = 3$，得分变为 $3$，数组变为 $[1, 2, 4]$；接着移除 $a_2 = 2$，得分变为 $5$，数组变为 $[1, 4]$；最后移除 $a_2 = 4$，得分变为 $9$。此时数组长度已小于 $k=2$，因此无法再执行任何操作。可以证明，最大得分为 $9$。

在第二个测试用例中，我们只能执行一次操作，即移除 $a_1 = 3$ 或 $a_4 = 2$。显然，移除 $a_1 = 3$ 可获得更高的得分 $3$。