作为一家初创公司的首席执行官,您希望为每位 $$$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$$$。