CF2264B.Knife's Pill Farm

Mr. Knife has drafted $n$ absurd posts for a channel on a chat platform. His goal is to farm pill emoji reactions. Unfortunately, the channel's pill-farming bot uses an unnecessarily elaborate scoring rule.

The drafts have absurdity ratings $a_1, a_2, \ldots, a_n$, which may be negative. Mr. Knife must publish exactly $m$ drafts in their original order. Their ratings form a subsequence$^{\text{∗}}$ $b$ of $a$ with length $m$.

His pill score starts at $0$. When he publishes the $i$-th chosen draft, the bot changes his score by $i \cdot (b_i - b_{i-1})$, where $b_0 = 0$. A negative change deducts points, and the score is allowed to become negative. Thus, his final pill score is $$ \sum_{i = 1}^{m} i \cdot (b_i - b_{i - 1}). $$

What is the maximum pill score Mr. Knife can obtain by choosing which drafts to publish?

$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) elements from arbitrary positions.

Mr. Knife 为某聊天平台上的一个频道草拟了 $n$ 篇荒诞帖子。他的目标是刷取药丸（pill）emoji 反应。不幸的是，该频道的“刷药丸”机器人采用了一种过分复杂的评分规则。

这些草稿的荒诞度评分为 $a_1, a_2, \ldots, a_n$，该值可能为负数。Mr. Knife 必须按原始顺序恰好发布其中 $m$ 篇草稿。这些被选中的草稿的评分构成原序列 $a$ 的一个长度为 $m$ 的子序列$^{\text{∗}}$ $b$。

他的药丸得分初始为 $0$。当他发布第 $i$ 个被选中的草稿时，机器人会将其得分改变 $i \cdot (b_i - b_{i-1})$，其中约定 $b_0 = 0$。负向变化将扣除分数，且总分允许为负数。因此，他最终的药丸得分为

$$\sum_{i = 1}^{m} i \cdot (b_i - b_{i - 1}).$$

通过选择发布哪些草稿，Mr. Knife 能获得的最高药丸得分是多少？

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

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 of each test case contains two integers $n$ and $m$ ($1 \le m \le n \le 2 \cdot 10^5$) — the number of drafts and the number of posts Mr. Knife must publish.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^7 \le a_i \le 10^7$) — the absurdity ratings of the drafts.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 2 \cdot 10^5$）——分别表示草稿数量和 Mr. Knife 必须发布的帖子数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^7 \le a_i \le 10^7$）——表示各草稿的荒谬度评分。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the maximum pill score Mr. Knife can obtain by publishing exactly $m$ drafts in their original order.

对于每个测试用例，输出一个整数——即 Mr. Knife 按原始顺序发布恰好 $m$ 篇草稿所能获得的最大药丸分数。

In the first test case, Mr. Knife can publish the drafts with ratings $[0, 1, 7]$. His final pill score is $$ 1 \cdot (0 - 0) + 2 \cdot (1 - 0) + 3 \cdot (7 - 1) = 20. $$

In the second test case, he can publish the drafts with ratings $[0, -4, 10]$. The second post deducts points, but the third post more than makes up for it. His final pill score is $$ 1 \cdot (0 - 0) + 2 \cdot (-4 - 0) + 3 \cdot (10 - (-4)) = 34. $$

在第一个测试用例中，Knife 先生可以发布评分为 $[0, 1, 7]$ 的草稿。他的最终“药丸分数”为

$$1 \cdot (0 - 0) + 2 \cdot (1 - 0) + 3 \cdot (7 - 1) = 20.$$

在第二个测试用例中，他可以发布评分为 $[0, -4, 10]$ 的草稿。第二篇帖子会扣分，但第三篇帖子的加分足以弥补并超出。他的最终“药丸分数”为

$$1 \cdot (0 - 0) + 2 \cdot (-4 - 0) + 3 \cdot (10 - (-4)) = 34.$$