CF2268A K Is Important

给你一个由 $n$ 个正整数组成的数组 $a$，以及一个整数参数 $k$。 只要数组中至少有 $k$ 个元素，你就需要对 $a$ 执行以下两种操作之一： - 移除 $a_k$ 并将其值加到你的分数上； - 移除 $a_{m-k+1}$ 并将其值加到你的分数上，其中 $m$ 是本次操作前数组的长度。 移除元素后，剩余元素保持相对顺序不变。 你的任务是，求你能获得的最大分数。

每组测试数据包含多组测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 10^4$）。每组测试用例的描述如下： 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 10^5$）——数组 $a$ 的长度和参数 $k$。 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示能够获得的最大分数。

在第一个测试用例中，我们可以先移除 $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$。 由 ChatGPT 5 翻译