← 返回题目列表

Codeforces · 1951/C

C. 囤票

中文机器翻译题面 查看原题

作为一家初创公司的首席执行官,您希望为每位 $$$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$$$ 门票所需的最低金额。

示例

输入 #1

4
4 2 3
8 6 4 2
4 2 8
8 6 4 2
5 100 1
10000 1 100 10 1000
6 3 9
5 5 5 5 5 5

输出 #1

10
64
1
72

注意

在第一个测试用例中,购买 $$$3$$$ 门票的最佳方式如下:

- 第一天购买 $$$0$$$ 门票。剩余天数的每张门票价格为 $$$[6, 4, 2]$$$。
- 第二天购买 $$$0$$$ 门票。剩余天数的每张门票价格为 $$$[4, 2]$$$。
- 第三天购买$$$1$$$门票,花费$$$4$$$。剩余一天的每张门票价格为 $$$[3]$$$。
- 第四天购买 $$$2$$$ 门票,费用为 $$$6$$$。

在第二个测试用例中,只有一种方法可以购买 $$$8$$$ 门票:

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