青
题号：NC295778
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}在魔法学院的期末考试中，小青面对着一份由 n 道魔法题目组成的试卷。每道题目都有一个魔法能量值，第 i 道题目的能量值为 a_i，代表题目蕴含的魔力强度。然而，小青发现自己完全不会解答这些题目，只能依靠魔法来选择答案，但是小青魔法也没有好好学，所以他的魔法一定会让他猜错 k 个题，并且这些错误的题目不会连续出现（即任意两道错误题目之间至少有一道正确题目）。
\hspace{15pt}这是魔法学院，所以考试的分数规则也和我们正常的考试不一样，考试最终得分由所有连续正确题目的能量值之和的最小值决定。例如：答案分布为 T,F,T,T,F,T（T 为正确，F 为错误），则连续正确题目的能量和分别为 a_1,a_3+a_4,a_6，最终得分为 \min\{a_1,a_3+a_4,a_6\}。
\hspace{15pt}小青想请你告诉她，在运气最好的情况下，她能获得的最高分数是多少，这关系到她能否获得魔法学院的奖学金！

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^5\right) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入两个整数 n,k\left(1\leq n\leq 10^5;\ 0\leq 2\times k\leq n+1;\ n\neq k\right)，表示题目数量和猜错的题目数量。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\cdots,a_n\left(1\leq a_i\leq 10^9\right)，表示 n 个题目魔法能量值。 

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^5。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行输出一个整数，表示在最好情况下，她能获得的最高分数是多少。
示例1

输入

复制 
3
5 0
1 1 1 1 1
6 3
6 6 6 6 6 6
3 2
5 8 9

输出

复制 
5
6
8