制限付き削除 - المسألة

Alice と Bob に長さ $N$ の整数配列 $A$ が与えられます。

Alice はちょうど $K$ 個の 1 を含む長さ $N$ の 2 進文字列 $B$ を 1 つ選びます。この文字列はゲーム全体を通して固定されます。

任意の時点において、インデックス $i$ は $B_i = 1$ のとき、かつそのときに限り保護されており、Bob は $B_i = 0$ のとき、かつそのときに限りインデックス $i$ を選ぶことができます。

Bob は 0 回以上の手番を行います。Bob の初期スコアは $0$ です。

1 回の手番で、Bob は以下の条件を満たすインデックス $i$ を選びます：

Bob は現在の値 $A_i$ を自身のスコアに加算し、この要素を $A$ から削除します。各削除の後、$|A|$ は $1$ 減少し、$A$ の残りの要素には $1$ から $|A|$ までのインデックスが振り直されます。

したがって、$B$ は固定された要素そのものではなく、現在のインデックス位置に対して適用されます。要素がシフトした後、同じ要素が保護されたり削除可能になったりすることがあります。

Bob が手番全体を通して選んだインデックスを順に $P_1, P_2, \dots, P_m$ とすると、それらは非増加でなければなりません。つまり、

$$P_1 \ge P_2 \ge \dots \ge P_m$$

を満たす必要があります。Bob は同じインデックスを複数回選んでも構いません。

Alice は Bob のスコアを最小化したいと考えており、Bob はそれを最大化したいと考えています。

両者が最適に行動したときの Bob の最終スコアを求めてください。

入力は以下の形式で与えられます：

T
N K
A1 A2 ... AN
...

各テストケースについて、Bob の最終スコアを表す 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

テストケース 1： Alice は $B = 10001$ を選ぶことができます。このとき、最初に Bob が利用できるインデックスは $2$、$3$、$4$ であり、その値はそれぞれ $-1$、$7$、$-3$ です。Bob はインデックス $3$ を 1 回選ぶ（値 $7$ を加算する）ことでスコア $7$ を確実に得ることができます。その後、次に選ぶインデックスはすべて $3$ 以下でなければならないため、インデックス $4$ は選べず、それ以降の合法な手番では非正の値しか加算されません。Alice は Bob が $7$ より良いスコアを取れないようにできるため、答えは $7$ です。
テストケース 2： $K = 0$ なので、Alice に選択肢はなく $B = 0000$ となります。すべてのインデックスを Bob は利用できますが、配列のすべての値が負です。どのような手番を行っても Bob のスコアは減少してしまうため、Bob の最適な行動は 1 回も手番を行わないことです。したがって、答えは $0$ です。
テストケース 3： $K = N$ なので、Alice に選択肢はなく $B = 1111$ となります。すべての位置が保護されているため、Bob には合法な手番がまったくありません。したがって、Bob のスコアは $0$ です。

QOJ.ac