题目描述

music 喜欢玩扑克牌！

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

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

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

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

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

输入格式

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

对于每组数据：

第一行输入三个正整数 $n,m,k$ 。

接下来一行输入 $n$ 个整数 $a_1,a_2,…,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 \times 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$。