CF1951C.Ticket Hoarding

作为一家初创公司的 CEO，你希望奖励你的 $k$ 名员工每人一张即将到来的演唱会门票。门票将在 $n$ 天内发售，通过时空穿梭，你已经预测到第 $i$ 天每张门票的价格为 $a_i$。然而，为了防止门票被囤积，演唱会主办方实施了如下措施：

• 每人每天最多只能购买 $m$ 张门票。
• 如果某人在第 $i$ 天购买了 $x$ 张门票，则从第 $i+1$ 天起，之后所有天数的每张门票价格都会增加 $x$。

例如，若 $a = [1, 3, 8, 4, 5]$，你在第 $1$ 天购买了 $2$ 张门票，总花费为 $2$，从第 $2$ 天起的价格变为 $[5, 10, 6, 7]$。如果你在第 $2$ 天又购买了 $3$ 张门票，则额外花费 $15$，从第 $3$ 天起的价格变为 $[13, 9, 10]$。

请你计算，购买 $k$ 张门票所需的最小总花费。

每个测试用例包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。接下来是每组测试用例的描述。

每组测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^9, 1 \le k \le \min(nm, 10^9)$），分别表示发售天数、每天最多可购买的门票数，以及最终需要购买的门票总数。

每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示未来 $n$ 天每张门票的价格。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每组测试用例，输出一个整数，表示恰好购买 $k$ 张门票所需的最小总花费。

在第一个测试用例中，购买 $3$ 张门票的一种最优方案如下：

• 第一天不买票。剩余天数的价格为 $[6, 4, 2]$。
• 第二天不买票。剩余天数的价格为 $[4, 2]$。
• 第三天买 $1$ 张门票，花费 $4$。剩余一天的价格为 $[3]$。
• 第四天买 $2$ 张门票，花费 $6$。

在第二个测试用例中，购买 $8$ 张门票只有一种方式：

• 第一天买 $2$ 张门票，花费 $16$。剩余天数的价格为 $[8, 6, 4]$。
• 第二天买 $2$ 张门票，花费 $16$。剩余天数的价格为 $[8, 6]$。
• 第三天买 $2$ 张门票，花费 $16$。剩余一天的价格为 $[8]$。
• 第四天买 $2$ 张门票，花费 $16$。

由 ChatGPT 4.1 翻译