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.

对于任意长度为 $m$ 的序列 $b$，我们定义其代价函数 $f(b)$ 为：

$$f(b) = m \cdot \sum_{i=1}^m b_i.$$

给定一个长度为 $n$ 的序列 $a$ 和一个整数 $k$。

你的任务是将序列 $a$ 恰好划分为 $k$ 个非空子序列$^{\text{∗}}$，记作 $s_1, s_2, \ldots, s_k$。原始序列 $a$ 中的每个元素必须且仅属于这 $k$ 个子序列中的一个。

求总代价的最小可能值：

$$\sum_{i=1}^k f(s_i).$$

$^{\text{∗}}$ 序列 $c$ 是序列 $d$ 的一个子序列，当且仅当 $c$ 可通过从 $d$ 中删除若干（可能为零个或全部）位于任意位置的元素而得到。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

第一行包含两个整数 $n$ 和 $k$（$1\le k\le n \le 2\cdot 10^5$）—— 分别表示序列的长度以及所需子序列的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$\mathbf{-10^9} \le a_i \le \mathbf{10^9}$）—— 序列 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $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$.

在第一个测试用例中，最优的划分方式是分成 $[1,-2]$ 和 $[3]$。总得分为 $2(1-2)+1(3)=1$。

在第二个测试用例中，唯一可能的划分方式是仅含 $1$ 个子序列 $[1,3,-2]$。得分为 $3(1+3-2)=6$。