يُعطى أليس وبوب مصفوفة أعداد صحيحة $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$.