#P18023. Restricted Removals

Restricted Removals

Restricted Removals

Alice 和 Bob 有一个长度为 NN 的整数数组 AA。

Alice 先选择一个长度为 NN、恰好含有 KK 个 1 的二进制串 BB,并在整场游戏中固定它。

Bob 的初始得分为 00。他可以进行任意次操作,也可以不操作。每次操作选择当前数组中的一个下标 ii,要求 Bi=0B_i=0,将当前的 AiA_i 加入得分,再删除这个元素。删除后数组长度减一,剩余元素重新从 11 开始编号。

特别注意,BB 作用于当前下标位置,而不是跟随原来的元素移动。原来被保护的元素在其他元素删除后,可能移到可删除的位置,反之亦然。

另外,Bob 各次操作选择的下标必须非递增。如果依次选择 P1,P2,…,PmP_1,P_2,\ldots,P_m,必须满足

P1≥P2≥⋯≥Pm.P_1\ge P_2\ge\cdots\ge P_m.

允许多次选择相同下标。Alice 希望 Bob 的最终得分尽可能小,Bob 希望得分尽可能大。求双方都采取最优策略时 Bob 的最终得分。

输入格式

第一行一个整数 TT。每组数据第一行两个整数 N,KN,K,第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

每组数据输出一行一个整数,表示 Bob 的最终得分。

数据范围

1≤T≤1051\le T\le10^5,1≤N≤60001\le N\le6000,0≤K≤N0\le K\le N,−109≤Ai≤109-10^9\le A_i\le10^9。

所有测试用例的 NN 之和不超过 10610^6,N2N^2 之和不超过 600026000^2。

样例 1

输入

6
5 2
4 -1 7 -3 2
4 0
-5 -2 -1 -3
4 4
2 -7 5 1
1 0
-1
2 1
0 1
3 1
1 -1 1

输出

7
0
0
0
1
1