Cho mảng \(A\) gồm \(N\) số nguyên không âm và số \(K\). Nhiệm vụ của bạn là hãy chia mảng \(A\) thành hai mảng con có kích cỡ \(K\) và \(N-K\) sao cho hiệu giữa tổng hai mảng con là lớn nhất. Ví dụ với mảng \(A\) = \({8, 4, 5, 2, 10}\), \(K=2\) ta có kết quả là \(17\) vì mảng \(A\) được chia thành hai mảng \({4, 2}\) và \({8, 5,10}\) có hiệu của hai mảng con là \(23-6=17\) là lớn nhất.

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm \(2\) dòng:
• Dòng thứ nhất đưa vào số phần tử của mảng \(N\) và số \(K\) (\(1 \leq K < N \leq 50\)).
• Dòng tiếp theo đưa vào \(N\) số \(A_i\) (\(1 \leq i \leq N, 0 \leq A_i \leq 1000\)) tương ứng với các phần tử của mảng \(A\); các số được viết cách nhau một vài khoảng trống.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
5 2
8 4 5 2 10
8 3
1 1 1 1 1 1 1 1

17
2