Ad Alice e Bob viene dato un array di interi $A$ di lunghezza $N$.

Alice sceglie una stringa binaria $B$ di lunghezza $N$ con esattamente $K$ uno, e questa stringa rimane fissa per tutta la partita.

In qualsiasi momento, l'indice $i$ è protetto se e solo se $B_i = 1$, e Bob può scegliere l'indice $i$ se e solo se $B_i = 0$.

Bob effettua zero o più mosse. Il punteggio di Bob inizialmente è uguale a $0$.

In una mossa, Bob sceglie un indice $i$ tale che:

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

Bob aggiunge il valore corrente $A_i$ al suo punteggio e rimuove questo elemento da $A$. Dopo ogni eliminazione, $|A|$ diminuisce di $1$, e gli elementi rimanenti di $A$ vengono reindicizzati da $1$ a $|A|$.

Pertanto, $B$ viene applicata alle posizioni degli indici correnti, non alle identità fisse degli elementi. Dopo gli scorrimenti, lo stesso elemento può diventare protetto o rimovibile.

Se Bob sceglie gli indici $P_1, P_2, \dots, P_m$ nel corso delle mosse, essi devono essere non crescenti, cioè:

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

Bob può scegliere lo stesso indice più volte.

Alice vuole minimizzare il punteggio di Bob, e Bob vuole massimizzarlo.

Trova il punteggio finale di Bob se entrambi i giocatori giocano in modo ottimale.

Input

L'input è fornito nel seguente formato:

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

Vincoli

• Tutti i valori di input sono numeri interi.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• È garantito che la somma di $N$ su tutti i casi di test non supera $10^6$.
• È garantito che la somma di $N^2$ su tutti i casi di test non supera $6000^2$.

Output

Per ogni caso di test, stampa un singolo numero intero — il punteggio finale di Bob.

Esempio

Input 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

Output 1

7
0
0
0
1
1

Note

• Caso di test 1: Alice può scegliere $B = 10001$. Allora, inizialmente, gli indici disponibili per Bob sono $2$, $3$ e $4$ con valori $-1$, $7$ e $-3$. Bob può garantirsi un punteggio di $7$ prendendo l'indice $3$ una volta (aggiungendo il valore $7$). Dopodiché, ogni indice scelto successivamente deve essere al massimo $3$, quindi l'indice $4$ non può essere scelto, e qualsiasi ulteriore mossa legale aggiunge un valore non positivo. Alice può fare in modo che Bob non possa fare meglio di $7$, quindi la risposta è $7$.
• Caso di test 2: Poiché $K = 0$, Alice non ha scelta, $B = 0000$. Tutti gli indici sono disponibili per Bob, ma ogni valore dell'array è negativo. Qualsiasi mossa diminuirebbe il punteggio di Bob, quindi la strategia ottimale di Bob è non fare alcuna mossa. Pertanto, la risposta è $0$.
• Caso di test 3: Poiché $K = N$, Alice non ha scelta, $B = 1111$. Ogni posizione è protetta, quindi Bob non ha alcuna mossa legale. Di conseguenza, il punteggio di Bob è $0$.