Alice og Bob fá heiltölufylki $A$ af lengd $N$.

Alice velur tvíundarstreng $B$ af lengd $N$ með nákvæmlega $K$ ásum, og þessi strengur er fastur allan leikinn.

Á hverju augnabliki er vísir $i$ varinn ef og aðeins ef $B_i = 1$, og Bob má velja vísi $i$ ef og aðeins ef $B_i = 0$.

Bob gerir núll eða fleiri leiki. Stig Bobs eru í upphafi jöfn $0$.

Í einum leik velur Bob vísi $i$ þannig að:

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

Bob bætir núverandi gildi $A_i$ við stigin sín og fjarlægir þetta stak úr $A$. Eftir hverja eyðingu minnkar $|A|$ um $1$, og stökin sem eftir eru í $A$ fá nýja vísa frá $1$ til $|A|$.

Þess vegna gildir $B$ um núverandi vísastöður, en ekki um föst auðkenni staka. Eftir hliðranir getur sama stakið orðið varið eða fjarlægjanlegt.

Ef Bob velur vísana $P_1, P_2, \dots, P_m$ í leikjum sínum verða þeir að veraekki-vaxandi, það er að segja,

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

Bob má velja sama vísinn oft.

Alice vill lágmarka stig Bobs og Bob vill hámarka þau.

Finndu lokastig Bobs ef báðir leikmenn spila á besta hátt.

Inntak

Inntakið er gefið á eftirfarandi sniði:

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

Skorður

• Öll inntaksgildi eru heiltölur.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Það er tryggt að summa $N$ yfir öll prófunartilvik fari ekki yfir $10^6$.
• Það er tryggt að summa $N^2$ yfir öll prófunartilvik fari ekki yfir $6000^2$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta eina heiltölu — lokastig Bobs.

Dæmi

Inntak 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

Úttak 1

7
0
0
0
1
1

Athugasemd

• Prófunartilvik 1: Alice getur valið $B = 10001$. Þá eru vísarnir sem Bob stendur til boða í upphafi $2$, $3$ og $4$ með gildin $-1$, $7$ og $-3$. Bob getur tryggt sér $7$ stig með því að taka vísi $3$ einu sinni (bætir við gildinu $7$). Eftir það verður hver næsti valinn vísir að vera í mesta lagi $3$, þannig að ekki er hægt að velja vísi $4$, og sérhver frekari löglegur leikur bætir við ekki-jákvæðu gildi. Alice getur þvingað fram að Bob geti ekki gert betur en $7$, svo svarið er $7$.
• Prófunartilvik 2: Þar sem $K = 0$ hefur Alice ekkert val, $B = 0000$. Allir vísar standa Bob til boða, en öll gildin í fylkinu eru neikvæð. Sérhver leikur myndi lækka stig Bobs, þannig að besti leikur Bobs er að gera engan leik. Þess vegna er svarið $0$.
• Prófunartilvik 3: Þar sem $K = N$ hefur Alice ekkert val, $B = 1111$. Hver staða er varin, þannig að Bob á engan löglegan leik. Því eru stig Bobs $0$.