Alice og Bob får oppgitt en heltallstabell $A$ med lengde $N$.

Alice velger en binærstreng $B$ med lengde $N$ med nøyaktig $K$ enere, og denne strengen er låst gjennom hele spillet.

Til enhver tid er indeks $i$ beskyttet hvis og bare hvis $B_i = 1$, og Bob kan velge indeks $i$ hvis og bare hvis $B_i = 0$.

Bob gjør null eller flere trekk. Bobs poengsum er i utgangspunktet lik $0$.

I ett trekk velger Bob en indeks $i$ slik at:

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

Bob legger den nåværende verdien $A_i$ til poengsummen sin og fjerner dette elementet fra $A$. Etter hver sletting reduseres $|A|$ med $1$, og de gjenværende elementene i $A$ blir omindeksert fra $1$ til $|A|$.

Derfor brukes $B$ på nåværende indeksposisjoner, ikke på faste elementidentiteter. Etter forskyvninger kan det samme elementet bli beskyttet eller mulig å fjerne.

Hvis Bob velger indeksene $P_1, P_2, \dots, P_m$ gjennom trekkene, må de være ikke-økende, det vil si

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

Bob kan velge samme indeks flere ganger.

Alice ønsker å minimere Bobs poengsum, og Bob ønsker å maksimere den.

Finn Bobs endelige poengsum hvis begge spillerne spiller optimalt.

Inndata

Inndataene gis i følgende format:

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

Begrensninger

• Alle inndataverdier er heltall.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Det er garantert at summen av $N$ over alle testtilfeller ikke overstiger $10^6$.
• Det er garantert at summen av $N^2$ over alle testtilfeller ikke overstiger $6000^2$.

Utdata

For hvert testtilfelle, skriv ut et enkelt heltall — Bobs endelige poengsum.

Eksempel

Inndata 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

Utdata 1

7
0
0
0
1
1

Merk

• Testtilfelle 1: Alice kan velge $B = 10001$. Da er indeksene som er tilgjengelige for Bob i starten $2$, $3$ og $4$ med verdiene $-1$, $7$ og $-3$. Bob kan garantere en poengsum på $7$ ved å ta indeks $3$ én gang (legger til verdien $7$). Etter det må hver neste valgte indeks være høyst $3$, så indeks $4$ kan ikke velges, og ethvert videre lovlig trekk legger til en ikke-positiv verdi. Alice kan tvinge gjennom at Bob ikke kan gjøre det bedre enn $7$, så svaret er $7$.
• Testtilfelle 2: Siden $K = 0$, har Alice ikke noe valg, $B = 0000$. Alle indekser er tilgjengelige for Bob, men hver verdi i tabellen er negativ. Ethvert trekk ville redusert Bobs poengsum, så Bobs optimale spill er å ikke gjøre noen trekk. Derfor er svaret $0$.
• Testtilfelle 3: Siden $K = N$, har Alice ikke noe valg, $B = 1111$. Hver posisjon er beskyttet, så Bob har ingen lovlige trekk i det hele tatt. Dermed er Bobs poengsum $0$.