Cho dãy \(a\) gồm \(n\) phần tử \(a_1,a_2,…,a_n\).

Độ đẹp của dãy con gồm \(k\) phần tử là tổng của \(k\) phần tử sau khi tăng gấp đôi mỗi số.

Yêu cầu: Chọn ra dãy con gồm \(k\) phần tử trong dãy sao cho độ đẹp của dãy con lớn nhất.

Input

• Dòng đầu tiên chứ số nguyên \(T (1 ≤ T ≤ 10)\) – là số bộ Test, với mỗi bộ Test

• Dòng 1: chứa hai số nguyên \(n,k (1 ≤ k ≤ n ≤ 10^5 )\);

• Dòng 2: chứa \(n\) số nguyên \(a_1,a_2,…,a_n (a_i ≤ 10^3 )\);

Output:

• Kết quả mỗi Test ghi trên một dòng là độ đẹp lớn nhất của dãy con gồm \(k\) phần tử.

Sample Input

2
5 3
1 4 1 3 1
3 1
2 5 1

Sample Output

16
10