题目描述

music 喜欢玩扑克牌！

现在有 \(n\) 张牌从上至下组成一个牌堆，从上数第 \(i\) 张牌上的点数为 \(a_i\)。

有 \(m\) 位玩家一起玩扑克牌，music 是第 \(k\) 名玩家。所有玩家需要按 \(1, 2, \dots, m\) 的顺序，依次从上至下摸牌。

music 认为，自己手上的牌点数总和越大越好，他作为游戏组织者，可以进行 至多一次 调整牌组的操作：

• 将牌堆从任意位置分开，得到 上、下 两堆牌。
• 将上面这堆牌整体移动到牌堆的下方（交换上下两堆牌）。

因为牌的数量和玩家的数量有点多，请你编写一个程序来帮 music 获得最大的点数和。

输入格式

第一行输入一个正整数 \(T\) 表示测试用例数量。

对于每组数据：

第一行输入三个正整数 \(n, m, k\)。

接下来一行输入 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)，自顶向下给出牌堆每张牌上的数字。

令 \(N_{tot}\) 表示所有测试组 \(n\) 之和。

• \(1 \le T \le 10^4, N_{tot} \le 2 \times 10^5\)。

对于每组数据：

\(1 \le k \le m \le n \le 2 \cdot 10^5, -10^9 \le a_i \le 10^9\)。

输出格式

对于每组数据：

输出一行一个整数，表示 music 可以获得的最大点数和。

样例输入

2
2 2 1
114514 1919810
3 1 1
1 -3 2

样例输出

1919810
0

提示

第一个测试用例有两张牌，两个玩家玩，music 可以通过一次操作 得到 \([1919810, 114514]\) 这个序列，然后自己第一个摸牌，得到 \(1919810\) 点。 第二个测试用例，只有 music 一个玩家，摸到的点数为 \(1 - 3 + 2 = 0\)。