Алисе и Бобу дан массив целых чисел $A$ длины $N$.

Алиса выбирает двоичную строку $B$ длины $N$, содержащую ровно $K$ единиц, и эта строка остаётся фиксированной на протяжении всей игры.

В любой момент времени индекс $i$ защищён тогда и только тогда, когда $B_i = 1$, а Боб может выбрать индекс $i$ тогда и только тогда, когда $B_i = 0$.

Боб делает ноль или более ходов. Изначально счёт Боба равен $0$.

За один ход Боб выбирает индекс $i$ такой, что:

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

Боб прибавляет текущее значение $A_i$ к своему счёту и удаляет этот элемент из $A$. После каждого удаления $|A|$ уменьшается на $1$, а оставшиеся элементы $A$ перенумеровываются от $1$ до $|A|$.

Таким образом, $B$ применяется к текущим позициям индексов, а не к фиксированным элементам. После сдвигов один и тот же элемент может стать защищённым или доступным для удаления.

Если на протяжении ходов Боб выбирает индексы $P_1, P_2, \dots, P_m$, они должны не возрастать, то есть

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

Боб может выбирать один и тот же индекс несколько раз.

Алиса хочет минимизировать счёт Боба, а Боб хочет максимизировать его.

Найдите итоговый счёт Боба при оптимальной игре обоих игроков.

Входные данные

Входные данные даны в следующем формате:

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

Ограничения

• Все входные значения являются целыми числами.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Гарантируется, что сумма $N$ по всем наборам входных данных не превышает $10^6$.
• Гарантируется, что сумма $N^2$ по всем наборам входных данных не превышает $6000^2$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — итоговый счёт Боба.

Пример

Входные данные 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

Выходные данные 1

7
0
0
0
1
1

Примечание

• Тестовый пример 1: Алиса может выбрать $B = 10001$. Тогда изначально Бобу доступны индексы $2$, $3$ и $4$ со значениями $-1$, $7$ и $-3$. Боб может гарантировать себе счёт $7$, взяв один раз индекс $3$ (прибавив значение $7$). После этого каждый следующий выбранный индекс должен быть не больше $3$, поэтому индекс $4$ выбрать нельзя, а любой дальнейший допустимый ход прибавляет неположительное значение. Алиса может добиться того, чтобы Боб не смог набрать больше $7$, поэтому ответ равен $7$.
• Тестовый пример 2: Так как $K = 0$, у Алисы нет выбора: $B = 0000$. Все индексы доступны Бобу, но все значения в массиве отрицательны. Любой ход уменьшил бы счёт Боба, поэтому оптимальная игра Боба — не делать ни одного хода. Следовательно, ответ равен $0$.
• Тестовый пример 3: Так как $K = N$, у Алисы нет выбора: $B = 1111$. Каждая позиция защищена, поэтому у Боба вообще нет допустимых ходов. Следовательно, счёт Боба равен $0$.