311217: CF1951C. Ticket Hoarding

C. Ticket Hoardingtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputMaître Gims - Est-ce que tu m'aimes ?ඞ

As the CEO of a startup company, you want to reward each of your $k$ employees with a ticket to the upcoming concert. The tickets will be on sale for $n$ days, and by some time travelling, you have predicted that the price per ticket at day $i$ will be $a_i$. However, to prevent ticket hoarding, the concert organizers have implemented the following measures:

• A person may purchase no more than $m$ tickets per day.
• If a person purchases $x$ tickets on day $i$, all subsequent days (i.e. from day $i+1$ onwards) will have their prices per ticket increased by $x$.

For example, if $a = [1, 3, 8, 4, 5]$ and you purchase $2$ tickets on day $1$, they will cost $2$ in total, and the prices from day $2$ onwards will become $[5, 10, 6, 7]$. If you then purchase $3$ more tickets on day $2$, they will cost in total an additional $15$, and the prices from day $3$ onwards will become $[13, 9, 10]$.

Find the minimum spending to purchase $k$ tickets.

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^9, 1 \le k \le \min(nm, 10^9)$) — the number of sale days, the maximum amount of ticket purchasable each day, and the number of tickets to be bought at the end.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the price per ticket for each of the upcoming $n$ days.

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

Output

For each test case, print one integer: the minimum amount of money needed to purchase exactly $k$ tickets.

ExampleInput

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

Output

10
64
1
72

Note

In the first test case, one optimal way to buy $3$ tickets is as follows:

• Buy $0$ tickets on the first day. The prices per ticket for the remaining days are $[6, 4, 2]$.
• Buy $0$ tickets on the second day. The prices per ticket for the remaining days are $[4, 2]$.
• Buy $1$ ticket on the third day with cost $4$. The price per ticket for the remaining day is $[3]$.
• Buy $2$ tickets on the fourth day with cost $6$.

In the second test case, there is only one way to buy $8$ tickets:

• Buy $2$ tickets on the first day with cost $16$. The prices per ticket for the remaining days are $[8, 6, 4]$.
• Buy $2$ tickets on the second day with cost $16$. The prices per ticket for the remaining days are $[8, 6]$.
• Buy $2$ tickets on the third day with cost $16$. The price per ticket for the remaining day is $[8]$.
• Buy $2$ tickets on the fourth day with cost $16$.

题目大意：你是一家初创公司的CEO，你想为你的每个员工提供一张即将到来的音乐会门票。门票将在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≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数n、m和k（1≤n≤3×10^5，1≤m≤10^9，1≤k≤min(nm, 10^9)）——销售天数、每天最多可购买的门票数量和最终需要购买的门票数量。

每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9）——接下来n天的每张门票价格。

保证所有测试用例的n之和不超过3×10^5。

输出数据格式：对于每个测试用例，输出一个整数：购买恰好k张门票所需的最小金额。题目大意：你是一家初创公司的CEO，你想为你的每个员工提供一张即将到来的音乐会门票。门票将在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≤t≤10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数n、m和k（1≤n≤3×10^5，1≤m≤10^9，1≤k≤min(nm, 10^9)）——销售天数、每天最多可购买的门票数量和最终需要购买的门票数量。 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9）——接下来n天的每张门票价格。 保证所有测试用例的n之和不超过3×10^5。 输出数据格式：对于每个测试用例，输出一个整数：购买恰好k张门票所需的最小金额。