Alicja i Bob otrzymują tablicę liczb całkowitych $A$ o długości $N$.

Alicja wybiera ciąg binarny $B$ o długości $N$ zawierający dokładnie $K$ jedynek; ciąg ten pozostaje stały przez całą grę.

W każdym momencie indeks $i$ jest chroniony wtedy i tylko wtedy, gdy $B_i = 1$, a Bob może wybrać indeks $i$ wtedy i tylko wtedy, gdy $B_i = 0$.

Bob wykonuje zero lub więcej ruchów. Początkowy wynik Boba wynosi $0$.

W jednym ruchu Bob wybiera indeks $i$ taki, że:

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

Bob dodaje bieżącą wartość $A_i$ do swojego wyniku i usuwa ten element z $A$. Po każdym usunięciu $|A|$ zmniejsza się o $1$, a pozostałe elementy tablicy $A$ są przeindeksowywane od $1$ do $|A|$.

W związku z tym ciąg $B$ odnosi się do bieżących pozycji indeksów, a nie do stałych tożsamości elementów. Po przesunięciach ten sam element może stać się chroniony lub możliwy do usunięcia.

Jeśli w kolejnych ruchach Bob wybiera indeksy $P_1, P_2, \dots, P_m$, muszą one być nierosnące, to znaczy:

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

Bob może wybrać ten sam indeks wielokrotnie.

Alicja chce zminimalizować wynik Boba, a Bob chce go zmaksymalizować.

Wyznacz końcowy wynik Boba przy założeniu, że oboje gracze grają optymalnie.

Wejście

Wejście podane jest w następującym formacie:

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

Ograniczenia

• Wszystkie wartości wejściowe są liczbami całkowitymi.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Gwarantuje się, że suma $N$ po wszystkich przypadkach testowych nie przekracza $10^6$.
• Gwarantuje się, że suma $N^2$ po wszystkich przypadkach testowych nie przekracza $6000^2$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą — końcowy wynik Boba.

Przykład

Wejście 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

Wyjście 1

7
0
0
0
1
1

Uwaga

• Przypadek testowy 1: Alicja może wybrać $B = 10001$. Wówczas początkowo dostępne dla Boba są indeksy $2$, $3$ oraz $4$ o wartościach $-1$, $7$ oraz $-3$. Bob może zagwarantować sobie wynik $7$, wybierając raz indeks $3$ (dodając wartość $7$). Po tym ruchu każdy kolejny wybrany indeks musi wynosić co najwyżej $3$, więc nie można wybrać indeksu $4$, a każdy kolejny dozwolony ruch dodaje wartość niedodatnią. Alicja może sprawić, że Bob nie uzyska wyniku lepszego niż $7$, zatem odpowiedzią jest $7$.
• Przypadek testowy 2: Ponieważ $K = 0$, Alicja nie ma wyboru i $B = 0000$. Wszystkie indeksy są dostępne dla Boba, ale każda wartość w tablicy jest ujemna. Każdy ruch zmniejszyłby wynik Boba, więc optymalną strategią Boba jest niewykonywanie żadnego ruchu. Zatem odpowiedzią jest $0$.
• Przypadek testowy 3: Ponieważ $K = N$, Alicja nie ma wyboru i $B = 1111$. Każda pozycja jest chroniona, więc Bob nie ma żadnego dozwolonego ruchu. Stąd wynik Boba wynosi $0$.