Alice et Bob reçoivent un tableau d'entiers $A$ de longueur $N$.

Alice choisit une chaîne binaire $B$ de longueur $N$ contenant exactement $K$ uns, et cette chaîne reste fixe pendant toute la partie.

À tout moment, l'indice $i$ est protégé si et seulement si $B_i = 1$, et Bob peut choisir l'indice $i$ si et seulement si $B_i = 0$.

Bob effectue zéro ou plusieurs coups. Le score de Bob vaut initialement $0$.

En un coup, Bob choisit un indice $i$ tel que :

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

Bob ajoute la valeur actuelle $A_i$ à son score et supprime cet élément de $A$. Après chaque suppression, $|A|$ diminue de $1$, et les éléments restants de $A$ sont réindexés de $1$ à $|A|$.

Par conséquent, $B$ s'applique aux positions d'indices actuelles, et non à des identités d'éléments fixes. Après les décalages, le même élément peut devenir protégé ou supprimable.

Si Bob choisit les indices $P_1, P_2, \dots, P_m$ au fil des coups, ils doivent être décroissants au sens large, c'est-à-dire :

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

Bob peut choisir le même indice plusieurs fois.

Alice veut minimiser le score de Bob, et Bob veut le maximiser.

Trouvez le score final de Bob si les deux joueurs jouent de manière optimale.

Entrée

L'entrée est donnée dans le format suivant :

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

Contraintes

• Toutes les valeurs d'entrée sont des entiers.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Il est garanti que la somme de $N$ sur l'ensemble des cas de test ne dépasse pas $10^6$.
• Il est garanti que la somme de $N^2$ sur l'ensemble des cas de test ne dépasse pas $6000^2$.

Sortie

Pour chaque cas de test, affichez un seul entier — le score final de Bob.

Exemple

Entrée 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

Sortie 1

7
0
0
0
1
1

Note

• Cas de test 1 : Alice peut choisir $B = 10001$. Alors, initialement, les indices disponibles pour Bob sont $2$, $3$ et $4$ avec les valeurs $-1$, $7$ et $-3$. Bob peut garantir un score de $7$ en prenant l'indice $3$ une fois (ajoutant la valeur $7$). Après cela, chaque indice choisi ensuite doit être au plus $3$, donc l'indice $4$ ne peut pas être choisi, et tout coup légal supplémentaire ajoute une valeur négative ou nulle. Alice peut forcer Bob à ne pas faire mieux que $7$, donc la réponse est $7$.
• Cas de test 2 : Comme $K = 0$, Alice n'a pas le choix, $B = 0000$. Tous les indices sont disponibles pour Bob, mais chaque valeur du tableau est négative. Tout coup diminuerait le score de Bob, donc le jeu optimal de Bob est de ne faire aucun coup. Par conséquent, la réponse est $0$.
• Cas de test 3 : Comme $K = N$, Alice n'a pas le choix, $B = 1111$. Chaque position est protégée, donc Bob n'a aucun coup légal. Ainsi, le score de Bob est $0$.