Alice und Bob erhalten ein ganzzahliges Array $A$ der Länge $N$.

Alice wählt eine Binärzeichenkette $B$ der Länge $N$ mit genau $K$ Einsen, und diese Zeichenkette bleibt für das gesamte Spiel fest.

Zu jedem Zeitpunkt ist der Index $i$ genau dann geschützt, wenn $B_i = 1$ gilt, und Bob darf den Index $i$ genau dann wählen, wenn $B_i = 0$ gilt.

Bob macht null oder mehr Züge. Bobs Punktzahl beträgt zu Beginn $0$.

In einem Zug wählt Bob einen Index $i$, sodass gilt:

• $B_i = 0$;
• $1 \le i \le |A|$.

Bob addiert den aktuellen Wert $A_i$ zu seiner Punktzahl und entfernt dieses Element aus $A$. Nach jedem Löschen verringert sich $|A|$ um $1$, und die verbleibenden Elemente von $A$ werden von $1$ bis $|A|$ neu indiziert.

Daher wird $B$ auf die aktuellen Indexpositionen angewendet und nicht auf feste Elementidentitäten. Nach Verschiebungen kann dasselbe Element geschützt oder entfernbar werden.

Wenn Bob über die Züge hinweg die Indizes $P_1, P_2, \dots, P_m$ wählt, müssen diese nicht-steigend sein, das heißt,

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

Bob darf denselben Index mehrmals wählen.

Alice möchte Bobs Punktzahl minimieren, und Bob möchte sie maximieren.

Bestimme Bobs Endpunktzahl, wenn beide Spieler optimal spielen.

Eingabe

Die Eingabe erfolgt im folgenden Format:

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

Einschränkungen

• Alle Eingabewerte sind ganze Zahlen.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Es wird garantiert, dass die Summe von $N$ über alle Testfälle $10^6$ nicht überschreitet.
• Es wird garantiert, dass die Summe von $N^2$ über alle Testfälle $6000^2$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzige ganze Zahl aus — Bobs Endpunktzahl.

Beispiel

Eingabe 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

Ausgabe 1

7
0
0
0
1
1

Hinweis

• Testfall 1: Alice kann $B = 10001$ wählen. Dann sind zu Beginn die für Bob verfügbaren Indizes $2$, $3$ und $4$ mit den Werten $-1$, $7$ und $-3$. Bob kann eine Punktzahl von $7$ garantieren, indem er einmal den Index $3$ nimmt (wodurch der Wert $7$ addiert wird). Danach muss jeder nächste gewählte Index höchstens $3$ sein, sodass Index $4$ nicht gewählt werden kann, und jeder weitere gültige Zug addiert einen nicht-positiven Wert. Alice kann erzwingen, dass Bob nicht besser als $7$ abschneiden kann, also lautet die Antwort $7$.
• Testfall 2: Da $K = 0$ ist, hat Alice keine Wahl, $B = 0000$. Alle Indizes stehen Bob zur Verfügung, aber jeder Array-Wert ist negativ. Jeder Zug würde Bobs Punktzahl verringern, sodass Bobs optimales Spiel darin besteht, keinen Zug zu machen. Daher lautet die Antwort $0$.
• Testfall 3: Da $K = N$ ist, hat Alice keine Wahl, $B = 1111$. Jede Position ist geschützt, sodass Bob überhaupt keinen gültigen Zug hat. Folglich beträgt Bobs Punktzahl $0$.