A Alice y Bob se les da un arreglo de enteros $A$ de longitud $N$.

Alice elige una cadena binaria $B$ de longitud $N$ con exactamente $K$ unos, y esta cadena permanece fija durante todo el juego.

En cualquier momento, el índice $i$ está protegido si y solo si $B_i = 1$, y Bob puede elegir el índice $i$ si y solo si $B_i = 0$.

Bob realiza cero o más movimientos. La puntuación de Bob inicialmente es igual a $0$.

En un movimiento, Bob elige un índice $i$ tal que:

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

Bob suma el valor actual $A_i$ a su puntuación y elimina este elemento de $A$. Después de cada eliminación, $|A|$ disminuye en $1$, y los elementos restantes de $A$ se vuelven a indexar desde $1$ hasta $|A|$.

Por lo tanto, $B$ se aplica a las posiciones de índice actuales, no a las identidades fijas de los elementos. Después de los desplazamientos, el mismo elemento puede pasar a estar protegido o a ser eliminable.

Si Bob elige los índices $P_1, P_2, \dots, P_m$ a lo largo de sus movimientos, estos deben ser no crecientes, es decir,

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

Bob puede elegir el mismo índice varias veces.

Alice quiere minimizar la puntuación de Bob, y Bob quiere maximizarla.

Halla la puntuación final de Bob si ambos jugadores juegan de manera óptima.

Entrada

La entrada se proporciona en el siguiente formato:

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

Restricciones

• Todos los valores de entrada son enteros.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Se garantiza que la suma de $N$ en todos los casos de prueba no supera $10^6$.
• Se garantiza que la suma de $N^2$ en todos los casos de prueba no supera $6000^2$.

Salida

Para cada caso de prueba, imprime un único entero — la puntuación final de Bob.

Ejemplo

Entrada 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

Salida 1

7
0
0
0
1
1

Nota

• Caso de prueba 1: Alice puede elegir $B = 10001$. Entonces, inicialmente, los índices disponibles para Bob son $2$, $3$ y $4$ con valores $-1$, $7$ y $-3$. Bob puede garantizar una puntuación de $7$ tomando el índice $3$ una vez (sumando el valor $7$). Después de eso, cada índice elegido a continuación debe ser como máximo $3$, por lo que el índice $4$ no se puede elegir, y cualquier movimiento legal adicional suma un valor no positivo. Alice puede forzar a que Bob no pueda obtener más de $7$, por lo que la respuesta es $7$.
• Caso de prueba 2: Como $K = 0$, Alice no tiene elección, $B = 0000$. Todos los índices están disponibles para Bob, pero todos los valores del arreglo son negativos. Cualquier movimiento disminuiría la puntuación de Bob, por lo que la jugada óptima de Bob es no realizar ningún movimiento. Por lo tanto, la respuesta es $0$.
• Caso de prueba 3: Como $K = N$, Alice no tiene elección, $B = 1111$. Todas las posiciones están protegidas, por lo que Bob no tiene ningún movimiento legal. Por consiguiente, la puntuación de Bob es $0$.