Knife 的药丸农场AI (CI翻译)
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.
$n$ 条荒谬帖子。他的目标是刷取药丸表情反应。不幸的是，该频道的刷药丸机器人采用了一套不必要地复杂的计分规则。AI (CI翻译)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$.
这些草稿的荒谬程度分别为 $a_1, a_2, \ldots, a_n$，其值可能为负数。Mr. Knife 必须按照原顺序恰好发布 $m$ 条草稿。它们的评分构成 $a$ 的一个长度为 $m$ 的子序列$^{\text{∗}}$ $b$。AI (CI翻译)
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}). $$
他的药丸得分初始为 $0$。当他发布第 $i$ 条选中的草稿时，机器人会将他的得分改变 $i \cdot (b_i - b_{i-1})$，其中 $b_0 = 0$。负数变化会扣除分数，并且得分可以变为负数。因此，他最终的药丸得分为 $$ \sum_{i = 1}^{m} i \cdot (b_i - b_{i - 1}). $$AI (CI翻译)
What is the maximum pill score Mr. Knife can obtain by choosing which drafts to publish?
通过选择要发布的草稿，Mr. Knife 能获得的最大药丸得分是多少？AI (CI翻译)
$^{\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.
$^{\text{∗}}$如果可以通过从序列 $b$ 的任意位置删除若干个（可以是零个或全部）元素得到序列 $a$，则称序列 $a$ 是序列 $b$ 的子序列。AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来描述各个测试用例。AI (CI翻译)
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.
每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 2 \cdot 10^5$）——草稿的数量，以及 Mr. Knife 必须发布的帖子数量。AI (CI翻译)
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.
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^7 \le a_i \le 10^7$）——各条草稿的荒谬程度。AI (CI翻译)
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)For each test case, print one integer — the maximum pill score Mr. Knife can obtain by publishing exactly $m$ drafts in their original order.
对于每个测试用例，输出一个整数——按照原顺序恰好发布 $m$ 条草稿时，Mr. Knife 能获得的最大药丸得分。AI (CI翻译)
Note
说明
AI (CI翻译)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. $$
在第一个测试用例中，Mr. Knife 可以发布评分为 $[0, 1, 7]$ 的草稿。他最终的药丸得分为 $$ 1 \cdot (0 - 0) + 2 \cdot (1 - 0) + 3 \cdot (7 - 1) = 20. $$AI (CI翻译)
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. $$
在第二个测试用例中，他可以发布评分为 $[0, -4, 10]$ 的草稿。第二条帖子会扣除分数，但第三条帖子带来的得分足以弥补损失。他最终的药丸得分为 $$ 1 \cdot (0 - 0) + 2 \cdot (-4 - 0) + 3 \cdot (10 - (-4)) = 34. $$
AI (CI翻译)
样例
6
5 3
0 8 1 7 3
4 3
0 -4 10 -2
4 2
0 5 -2 4
6 3
0 9 8 7 6 5
1 1
7
3 2
5 -100 4
20
34
10
15
7
108
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。