Алісі та Бобу задано масив цілих чисел $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$.