Alice 同埋 Bob 得到咗一個長度為 $N$ 嘅整數數組 $A$。

Alice 揀一個長度為 $N$ 而且恰好有 $K$ 個一嘅二進制字符串 $B$，呢個字符串喺成個遊戲過程入面保持不變。

喺任何時刻，下標 $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 可以透過揀一次下標 $3$（加上數值 $7$）嚟保證獲得 $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$。