Alice dan Bob diberikan sebuah array bilangan bulat $A$ dengan panjang $N$.

Alice memilih sebuah string biner $B$ dengan panjang $N$ yang memiliki tepat $K$ angka satu, dan string ini tetap untuk keseluruhan permainan.

Pada setiap saat, indeks $i$ terlindungi jika dan hanya jika $B_i = 1$, dan Bob boleh memilih indeks $i$ jika dan hanya jika $B_i = 0$.

Bob melakukan nol langkah atau lebih. Skor Bob pada awalnya sama dengan $0$.

Dalam satu langkah, Bob memilih sebuah indeks $i$ sedemikian sehingga:

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

Bob menambahkan nilai saat ini $A_i$ ke skornya dan menghapus elemen ini dari $A$. Setelah setiap penghapusan, $|A|$ berkurang sebanyak $1$, dan elemen-elemen yang tersisa dari $A$ diberi indeks ulang dari $1$ hingga $|A|$.

Oleh karena itu, $B$ diterapkan pada posisi indeks saat ini, bukan pada identitas elemen yang tetap. Setelah pergeseran, elemen yang sama dapat menjadi terlindungi atau dapat dihapus.

Jika Bob memilih indeks $P_1, P_2, \dots, P_m$ di sepanjang langkah-langkahnya, indeks-indeks tersebut harus tidak meningkat, yaitu:

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

Bob boleh memilih indeks yang sama beberapa kali.

Alice ingin meminimalkan skor Bob, dan Bob ingin memaksimalkannya.

Carilah skor akhir Bob jika kedua pemain bermain secara optimal.

Masukan

Masukan diberikan dalam format berikut:

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

Batasan

• Semua nilai masukan adalah bilangan bulat.
• $1 \le T \le 10^5$
• $1 \le N \le 6000$
• $0 \le K \le N$
• $-10^9 \le A_i \le 10^9$
• Dijamin bahwa jumlah dari $N$ di semua kasus uji tidak melebihi $10^6$.
• Dijamin bahwa jumlah dari $N^2$ di semua kasus uji tidak melebihi $6000^2$.

Keluaran

Untuk setiap kasus uji, cetak sebuah bilangan bulat — skor akhir Bob.

Contoh

Masukan 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

Keluaran 1

7
0
0
0
1
1

Catatan

• Kasus uji 1: Alice dapat memilih $B = 10001$. Maka, pada awalnya, indeks yang tersedia bagi Bob adalah $2$, $3$, dan $4$ dengan nilai $-1$, $7$, dan $-3$. Bob dapat menjamin skor sebesar $7$ dengan mengambil indeks $3$ satu kali (menambahkan nilai $7$). Setelah itu, setiap indeks yang dipilih berikutnya harus paling banyak $3$, sehingga indeks $4$ tidak dapat dipilih, dan langkah sah selanjutnya hanya akan menambahkan nilai tak positif. Alice dapat memaksa agar Bob tidak bisa mendapatkan hasil lebih baik dari $7$, sehingga jawabannya adalah $7$.
• Kasus uji 2: Karena $K = 0$, Alice tidak punya pilihan selain $B = 0000$. Semua indeks tersedia bagi Bob, tetapi setiap nilai array adalah negatif. Langkah apa pun akan mengurangi skor Bob, sehingga permainan optimal Bob adalah tidak melakukan langkah sama sekali. Oleh karena itu, jawabannya adalah $0$.
• Kasus uji 3: Karena $K = N$, Alice tidak punya pilihan selain $B = 1111$. Setiap posisi terlindungi, sehingga Bob sama sekali tidak memiliki langkah yang sah. Dengan demikian, skor Bob adalah $0$.