題目描述

小紀正在舉辦一個攤位遊戲，他會把 N 個整數 A₁, A₂, A₃, …, A_N 排成一列。第一種是可以任意選取其中 k (k ≤ N) 個數字 (不需要連續) 並拿下，而拿下的數字總和就是該選手獲得的分數；第二種是需要張開雙臂，把臂內的所有數字全數拿下，拿下的數字總和就是該選手獲得的分數。也可以放棄，這樣得到的分數就是 0。

小紀為了不吃虧，早就在那些整數裏加了一些負數。現在，請你計算最高可能達到的分數是多少？

輸入格式

第一行一個正整數 T，表示接下來有 T 個測試用例。

每個測試用例兩行：

第一行兩個正整數 N, M。其中，M 表示第 M 種模式。

第二行 N 個整數，表示 A₁, A₂, A₃, …, A_N，保證 -10⁹ ≤ A_i ≤ 10⁹。

輸出格式

對於每個測試用例，隔行輸出最高可能達到的分數。

Samples

5
5 2
1 2 3 4 5
6 1
-3 5 -6 -7 9 3
3 1
-1 -2 -4
3 2
-1 -2 -4
7 2
2 -4 3 -1 2 -4 3

15
17
0
0
4

提示

數據範圍

10 分: T ≤ 5, N ≤ 10, M ≤ 1

25 分: T ≤ 10, N ≤ 10³, M ≤ 2

50 分: T ≤ 20, N ≤ 2 × 10⁴, M ≤ 2

100 分: T ≤ 30, N ≤ 10⁵, M ≤ 2

原始資料

• Zero1 題號：b279
• Hydro 題號：Z1279
• Locale：zh_TW
• Display：practice