Alice och Bob får en heltalsarray $A$ med längden $N$.

Alice väljer en binär sträng $B$ med längden $N$ med exakt $K$ ettor, och denna sträng är fixerad under hela spelet.

Vid varje tidpunkt är index $i$ skyddat om och endast om $B_i = 1$, och Bob får välja index $i$ om och endast om $B_i = 0$.

Bob gör noll eller flera drag. Bobs poäng är från början lika med $0$.

I ett drag väljer Bob ett index $i$ sådant att:

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

Bob lägger till det aktuella värdet $A_i$ till sin poäng och tar bort detta element från $A$. Efter varje borttagning minskar $|A|$ med $1$, och de återstående elementen i $A$ omindexeras från $1$ till $|A|$.

Därför tillämpas $B$ på aktuella indexpositioner, inte på fasta elementidentiteter. Efter förskjutningar kan samma element bli skyddat eller borttagbart.

Om Bob väljer indexen $P_1, P_2, \dots, P_m$ under dragen måste de vara icke-växande, det vill säga

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

Bob får välja samma index flera gånger.

Alice vill minimera Bobs poäng, och Bob vill maximera den.

Hitta Bobs slutpoäng om båda spelarna spelar optimalt.

Indata

Indata ges i följande format:

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

Begränsningar

• Alla indatavärden är heltal.
• $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 garanteras att summan av $N$ över alla testfall inte överstiger $10^6$.
• Det garanteras att summan av $N^2$ över alla testfall inte överstiger $6000^2$.

Utdata

För varje testfall, skriv ut ett enda heltal — Bobs slutpoäng.

Exempel

Indata 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

Förklaring

• Testfall 1: Alice kan välja $B = 10001$. Då är de index som är tillgängliga för Bob från början $2$, $3$ och $4$ med värdena $-1$, $7$ och $-3$. Bob kan garantera en poäng på $7$ genom att ta index $3$ en gång (vilket lägger till värdet $7$). Efter det måste varje nästa valt index vara högst $3$, så index $4$ kan inte väljas, och varje ytterligare giltigt drag lägger till ett icke-positivt värde. Alice kan tvinga fram att Bob inte kan nå bättre än $7$, så svaret är $7$.
• Testfall 2: Eftersom $K = 0$ har Alice inget val, $B = 0000$. Alla index är tillgängliga för Bob, men varje arrayvärde är negativt. Varje drag skulle minska Bobs poäng, så Bobs optimala spel är att inte göra något drag alls. Därför är svaret $0$.
• Testfall 3: Eftersom $K = N$ har Alice inget val, $B = 1111$. Varje position är skyddad, så Bob har inget giltigt drag alls. Alltså är Bobs poäng $0$.