CF1837F.Editorial for Two

Berland Intercollegiate Contest has just finished. Monocarp and Polycarp, as the jury, are going to conduct an editorial. Unfortunately, the time is limited, since they have to finish before the closing ceremony.

There were $n$ problems in the contest. The problems are numbered from $1$ to $n$. The editorial for the $i$-th problem takes $a_i$ minutes. Monocarp and Polycarp are going to conduct an editorial for exactly $k$ of the problems.

The editorial goes as follows. They have a full problemset of $n$ problems before them, in order. They remove $n - k$ problems without changing the order of the remaining $k$ problems. Then, Monocarp takes some prefix of these $k$ problems (possibly, an empty one or all problems). Polycarp takes the remaining suffix of them. After that, they go to different rooms and conduct editorials for their problems in parallel. So, the editorial takes as much time as the longer of these two does.

Please, help Monocarp and Polycarp to choose the problems and the split in such a way that the editorial finishes as early as possible. Print the duration of the editorial.

Berland 大学联赛刚刚结束。裁判 Monocarp 和 Polycarp 将要进行赛题讲解（editorial）。不幸的是，时间非常有限，因为他们必须在闭幕式开始前完成全部讲解。

本次比赛共有 $n$ 道题目，编号从 $1$ 到 $n$。讲解第 $i$ 道题需要 $a_i$ 分钟。Monocarp 和 Polycarp 将恰好讲解其中 $k$ 道题。

讲解流程如下：他们面前有一份按顺序排列的完整题集（共 $n$ 道题）。他们从中移除 $n - k$ 道题，但保持剩余 $k$ 道题的相对顺序不变。接着，Monocarp 选择这 $k$ 道题的一个前缀（可以为空，也可以是全部 $k$ 道题），Polycarp 则负责剩下的后缀。随后，他们分别前往不同房间，并行地讲解各自分配到的题目。因此，整个讲解过程的总耗时等于两人中耗时更长者的时间。

请帮助 Monocarp 和 Polycarp 选择保留的题目以及前缀/后缀的划分方式，使得讲解尽早完成。输出该最短可能的总耗时。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$) — the number of problems in the full problemset and the number of problems Monocarp and Polycarp are going to conduct an editorial for.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the time each editorial takes.

The sum of $n$ over all testcases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \cdot 10^5$）—— 分别表示完整题目集中的题目数量，以及 Monocarp 和 Polycarp 将要进行题解讲解的题目数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 表示每道题的题解讲解所需时间。

所有测试用例的 $n$ 值之和不超过 $3 \cdot 10^5$。

For each testcase, print a single integer — the smallest amount of time the editorial takes, if Monocarp and Polycarp can choose which $k$ of $n$ problems to conduct an editorial for and how to split them among themselves.

对于每组测试数据，输出一个整数——即在 Monocarp 和 Polycarp 可以自由选择 $n$ 道题目中的任意 $k$ 道题进行讲解，并自由分配讲解任务的前提下，讲解所耗费的最短总时间。