Alicelle ja Bobille annetaan kokonaislukutaulukko $A$, jonka pituus on $N$.

Alice valitsee pituuden $N$ binäärimerkkijonon $B$, jossa on täsmälleen $K$ ykköstä, ja tämä merkkijono pysyy samana koko pelin ajan.

Minä tahansa hetkenä indeksi $i$ on suojattu jos ja vain jos $B_i = 1$, ja Bob saa valita indeksin $i$ jos ja vain jos $B_i = 0$.

Bob tekee nolla siirtoa tai enemmän. Bobin pistemäärä on aluksi $0$.

Yhdessä siirrossa Bob valitsee indeksin $i$ siten, että:

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

Bob lisää nykyisen arvon $A_i$ pistemääräänsä ja poistaa tämän alkion taulukosta $A$. Jokaisen poiston jälkeen $|A|$ pienenee luvulla $1$, ja taulukon $A$ jäljelle jäävät alkiot indeksoidaan uudelleen välille $1$ – $|A|$.

Näin ollen merkkijonoa $B$ sovelletaan nykyisiin indeksipaikkoihin eikä kiinteisiin alkioihin. Siirtymien jälkeen sama alkio voi muuttua suojatuksi tai poistettavaksi.

Jos Bob valitsee siirtojensa aikana indeksit $P_1, P_2, \dots, P_m$, niiden on oltava ei-kasvavia, eli

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

Bob saa valita saman indeksin useita kertoja.

Alice haluaa minimoida Bobin pistemäärän, ja Bob haluaa maksimoida sen.

Etsi Bobin lopullinen pistemäärä, jos molemmat pelaajat pelaavat optimaalisesti.

Syöte

Syöte annetaan seuraavassa muodossa:

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

Rajoitukset

• Kaikki syötearvot ovat kokonaislukuja.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• On taattu, että arvojen $N$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.
• On taattu, että arvojen $N^2$ summa yli kaikkien testitapausten ei ylitä arvoa $6000^2$.

Tuloste

Tulosta jokaista testitapausta kohden yksi kokonaisluku — Bobin lopullinen pistemäärä.

Esimerkki

Syöte 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

Tuloste 1

7
0
0
0
1
1

Huomautus

• Testitapaus 1: Alice voi valita $B = 10001$. Tällöin aluksi Bobin käytettävissä olevat indeksit ovat $2$, $3$ ja $4$, joiden arvot ovat $-1$, $7$ ja $-3$. Bob voi varmistaa pistemäärän $7$ valitsemalla indeksin $3$ kerran (lisäten arvon $7$). Tämän jälkeen jokaisen seuraavaksi valittavan indeksin on oltava enintään $3$, joten indeksiä $4$ ei voida valita, ja mikä tahansa muu laillinen siirto lisää ei-positiivisen arvon. Alice voi pakottaa pelin niin, ettei Bob voi saada parempaa tulosta kuin $7$, joten vastaus on $7$.
• Testitapaus 2: Koska $K = 0$, Alicella ei ole valinnanvaraa, vaan $B = 0000$. Kaikki indeksit ovat Bobin käytettävissä, mutta jokainen taulukon arvo on negatiivinen. Mikä tahansa siirto pienentäisi Bobin pistemäärää, joten Bobin optimaalinen pelitapa on olla tekemättä yhtään siirtoa. Siispä vastaus on $0$.
• Testitapaus 3: Koska $K = N$, Alicella ei ole valinnanvaraa, vaan $B = 1111$. Jokainen paikka on suojattu, joten Bobilla ei ole lainkaan laillisia siirtoja. Näin ollen Bobin pistemäärä on $0$.