Độ đẹp nhân đôi

Trong một dự án nghiên cứu mới, FullHouse Dev đang tìm hiểu về các thuật toán tối ưu hóa mảng. Họ đặc biệt quan tâm đến việc làm thế nào để tối đa hóa "độ đẹp" của một mảng thông qua các phép biến đổi.

Bài toán

Cho một mảng \(A\) có độ dài \(n\). Bạn có thể chọn \(k\) chỉ số khác nhau và nhân đôi giá trị của phần tử tại các vị trí đó.

Độ đẹp của mảng được định nghĩa là tổng của bất kỳ mảng con nào có độ dài \(m\). Hãy tìm độ đẹp lớn nhất có thể đạt được sau khi hoán vị mảng \(A\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Dòng đầu tiên của mỗi test case chứa hai số nguyên \(n\) và \(k\).
• Dòng thứ hai của mỗi test case chứa \(n\) số nguyên, biểu diễn các phần tử của mảng.

OUTPUT FORMAT:

• Với mỗi test case, in ra độ đẹp lớn nhất có thể đạt được sau khi hoán vị mảng \(A\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 2 \times 10^5\)
• \(1 \leq k, m \leq n\)
• \(1 \leq A_i \leq 10^9\)

Ví dụ

INPUT

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

OUTPUT

16
10

Giải thích

• Ở test case đầu tiên, ta có thể chọn các chỉ số 1, 2 và 3 (đánh số từ 1). Mảng \(A\) trở thành \([2,8,2,3,1]\). Hoán vị tạo ra độ đẹp lớn nhất là \([8,3,2,2,1]\). Do đó, đáp án là 16.

• Ở test case thứ hai, ta có thể chọn chỉ số 1. Mảng \(A\) trở thành \([4,5,1]\). Hoán vị tạo ra độ đẹp lớn nhất là \([5,4,1]\). Do đó, đáp án là 10.