Alice และ Bob ได้รับอาร์เรย์ของจำนวนเต็ม $A$ ที่มีความยาว $N$

Alice เลือกสตริงฐานสอง $B$ ที่มีความยาว $N$ ซึ่งมีเลขหนึ่งอยู่ $K$ ตัวพอดี และสตริงนี้จะถูกตรึงไว้ตลอดทั้งเกม

ในขณะใดๆ ดัชนี $i$ จะได้รับการป้องกันก็ต่อเมื่อ $B_i = 1$ และ Bob สามารถเลือกดัชนี $i$ ได้ก็ต่อเมื่อ $B_i = 0$

Bob ทำการเดินศูนย์ครั้งหรือมากกว่า คะแนนเริ่มต้นของ Bob เท่ากับ $0$

ในการเดินหนึ่งครั้ง Bob จะเลือกดัชนี $i$ ซึ่งทำให้:

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

Bob จะบวกค่าปัจจุบันของ $A_i$ เข้ากับคะแนนของเขา และลบสมาชิกนี้ออกจาก $A$ หลังจากการลบแต่ละครั้ง $|A|$ จะลดลง $1$ และสมาชิกที่เหลือของ $A$ จะถูกจัดลำดับดัชนีใหม่ตั้งแต่ $1$ ถึง $|A|$

ดังนั้น $B$ จึงถูกนำไปใช้กับตำแหน่งดัชนีปัจจุบัน ไม่ใช่ตัวตนที่ตายตัวของสมาชิก หลังจากการเลื่อนตำแหน่ง สมาชิกตัวเดิมอาจจะกลายเป็นได้รับการป้องกันหรือสามารถถูกลบได้

หาก Bob เลือกดัชนี $P_1, P_2, \dots, P_m$ ในการเดินแต่ละครั้ง ดัชนีเหล่านั้นจะต้องไม่เพิ่มขึ้น นั่นคือ:

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

Bob สามารถเลือกดัชนีเดิมซ้ำหลายครั้งได้

Alice ต้องการทำให้คะแนนของ Bob น้อยที่สุด และ Bob ต้องการทำให้คะแนนของเขามากที่สุด

จงหาคะแนนสุดท้ายของ Bob หากผู้เล่นทั้งสองเล่นอย่างเหมาะสมที่สุด

ข้อมูลนำเข้า

ข้อมูลนำเข้ามีรูปแบบดังต่อไปนี้:

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$

ข้อมูลส่งออก

สำหรับแต่ละชุดทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งจำนวน — คะแนนสุดท้ายของ Bob

ตัวอย่าง

ข้อมูลนำเข้า 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: Alice สามารถเลือก $B = 10001$ ได้ ดังนั้น ในตอนเริ่มต้น ดัชนีที่ Bob เลือกได้คือ $2$, $3$ และ $4$ ซึ่งมีค่าเป็น $-1$, $7$ และ $-3$ ตามลำดับ Bob สามารถรับประกันคะแนนที่ $7$ ได้โดยการเลือกดัชนี $3$ หนึ่งครั้ง (บวกค่า $7$ เข้าไป) หลังจากนั้น ดัชนีที่เลือกในครั้งถัดไปทุกตัวจะต้องมีค่าไม่เกิน $3$ ดังนั้นจึงไม่สามารถเลือกดัชนี $4$ ได้ และการเดินที่ถูกต้องใดๆ หลังจากนั้นจะเป็นการบวกค่าที่ไม่เป็นบวก Alice สามารถบังคับไม่ให้ Bob ทำคะแนนได้ดีกว่า $7$ ดังนั้นคำตอบคือ $7$
• ชุดทดสอบที่ 2: เนื่องจาก $K = 0$ ทำให้ Alice ไม่มีทางเลือกอื่นนอกจาก $B = 0000$ ดัชนีทั้งหมดสามารถถูกเลือกโดย Bob ได้ แต่ค่าในอาร์เรย์ทุกตัวเป็นค่าลบ การเดินใดๆ จะทำให้คะแนนของ Bob ลดลง ดังนั้นการเล่นที่เหมาะสมที่สุดของ Bob คือการไม่เดินเลย ดังนั้นคำตอบคือ $0$
• ชุดทดสอบที่ 3: เนื่องจาก $K = N$ ทำให้ Alice ไม่มีทางเลือกอื่นนอกจาก $B = 1111$ ทุกตำแหน่งได้รับการป้องกัน ดังนั้น Bob จึงไม่มีตาเดินที่ถูกต้องเลย เพราะฉะนั้น คะแนนของ Bob คือ $0$