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$。