CF2183H Minimise Cost

For any sequence $ b $ of length $ m $ , we define its cost function $ f(b) $ as: $$$ f(b) = m \cdot \sum_{i=1}^m b_i. $$$ You are given a sequence $ a $ of length $ n $ and an integer $ k $ . Your task is to partition the sequence $ a $ into exactly $ k $ non-empty subsequences $ ^{\text{∗}} $ , denoted as $ s_1, s_2, \ldots, s_k $ . Every element of the original sequence $ a $ must belong to exactly one of these subsequences. Find the minimum possible value of the total cost: $$$ \sum_{i=1}^k f(s_i). $$$ $ ^{\text{∗}} $ A sequence $ c $ is a subsequence of a sequence $ d $ if $ c $ can be obtained from $ d $ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line contains two integers $ n $ and $ k $ ( $ 1\le k\le n \le 2\cdot 10^5 $ ) — the length of the sequence and the number of subsequences required. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ \mathbf{-10^9} \le a_i \le \mathbf{10^9} $ ) — the elements of the sequence $ a $ . It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, output a single integer – the minimum sum of cost over all subsequences.

In the first test case, it is optimal to split into $ [1,-2] $ and $ [3] $ . The total score is $ 2(1-2)+1(3)=1 $ . In the second test case, the only possible way to partition is with $ 1 $ subsequence $ [1,3,-2] $ . The score is $ 3(1+3-2)=6 $ .