Alice và Bob được cho một mảng số nguyên $A$ có độ dài $N$.

Alice chọn một xâu nhị phân $B$ có độ dài $N$ chứa đúng $K$ chữ số 1, và xâu này được giữ cố định trong suốt trò chơi.

Tại bất kỳ thời điểm nào, chỉ số $i$ được bảo vệ khi và chỉ khi $B_i = 1$, và Bob chỉ có thể chọn chỉ số $i$ khi và chỉ khi $B_i = 0$.

Bob thực hiện không hoặc nhiều nước đi. Điểm số ban đầu của Bob bằng $0$.

Trong một nước đi, Bob chọn một chỉ số $i$ sao cho:

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

Bob cộng giá trị hiện tại $A_i$ vào điểm số của mình và xóa phần tử này khỏi $A$. Sau mỗi lần xóa, $|A|$ giảm đi $1$, và các phần tử còn lại của $A$ được đánh số lại từ $1$ đến $|A|$.

Do đó, $B$ được áp dụng cho các vị trí chỉ số hiện tại chứ không phải cho danh tính cố định của phần tử. Sau khi dịch chuyển, cùng một phần tử có thể trở thành được bảo vệ hoặc có thể bị xóa.

Nếu Bob chọn các chỉ số $P_1, P_2, \dots, P_m$ qua các nước đi, chúng phải tạo thành một dãy không tăng, nghĩa là:

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

Bob có thể chọn cùng một chỉ số nhiều lần.

Alice muốn cực tiểu hóa điểm số của Bob, còn Bob muốn cực đại hóa nó.

Hãy tìm điểm số cuối cùng của Bob nếu cả hai người chơi đều chơi tối ưu.

Dữ liệu vào

Dữ liệu vào được cho theo định dạng sau:

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

Giới hạn

• Tất cả các giá trị đầu vào đều là số nguyên.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Đảm bảo rằng tổng của $N$ trên tất cả các bộ test không vượt quá $10^6$.
• Đảm bảo rằng tổng của $N^2$ trên tất cả các bộ test không vượt quá $6000^2$.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên duy nhất — điểm số cuối cùng của Bob.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

7
0
0
0
1
1

Giải thích

• Test case 1: Alice có thể chọn $B = 10001$. Khi đó, ban đầu, các chỉ số mà Bob có thể chọn là $2$, $3$ và $4$ với các giá trị tương ứng là $-1$, $7$ và $-3$. Bob có thể đảm bảo đạt được điểm số là $7$ bằng cách chọn chỉ số $3$ một lần (cộng thêm giá trị $7$). Sau đó, mọi chỉ số được chọn tiếp theo phải tối đa là $3$, vì vậy không thể chọn chỉ số $4$, và bất kỳ nước đi hợp lệ nào tiếp theo cũng chỉ cộng thêm một giá trị không dương. Alice có thể ép buộc để Bob không thể đạt điểm cao hơn $7$, vì vậy đáp án là $7$.
• Test case 2: Vì $K = 0$, Alice không có lựa chọn nào khác ngoài $B = 0000$. Tất cả các chỉ số đều khả dụng cho Bob, nhưng mọi giá trị trong mảng đều âm. Bất kỳ nước đi nào cũng sẽ làm giảm điểm của Bob, vì vậy cách chơi tối ưu của Bob là không thực hiện nước đi nào. Do đó, đáp án là $0$.
• Test case 3: Vì $K = N$, Alice không có lựa chọn nào khác ngoài $B = 1111$. Mọi vị trí đều được bảo vệ, nên Bob hoàn toàn không có nước đi hợp lệ nào. Do đó, điểm số của Bob là $0$.