Ticket Hoarding
Contest: Codeforces Global Round 25
Difficulty rating: 1400
Tags: greedy, math, sortings

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 format:
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 format:
For each test case, print one integer: the minimum amount of money needed to purchase exactly $$$k$$$ tickets.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
10
64
1
72

Editorial:
Note: we will present the intuitive idea first; the formal proof follows later.
Let's try to find a way to interpret the raised price at day $$$i$$$ from buying on earlier days. We know that every ticket bought on an earlier day than $$$i$$$ raised the price per ticket $$$i$$$ by $$$1$$$; in turn, this "additional tax" will be added to our total cost every time a ticket is bought on day $$$i$$$. Parsing in a different way, every pair of ticket where one is bought before day $$$i$$$ and one is bought on day $$$i$$$ adds $$$1$$$ additional tax to the total cost, so the final additional tax is exactly "the number of pair of tickets that were bought on different days".
We now try to find a way to optimize both the base cost and the total additional tax. Observe that the same greedy strategy of "take as many cheap tickets as possible" works for both of them (obviously works for the first quantity, and for the second quantity it works because we're limiting the number of pair of tickets bought on different days). Implementing this gives an $$$O(n \log n)$$$ solution.
— — —
Formally, suppose we buy $$$b_1, b_2, \ldots, b_n$$$ tickets on day $$$1, 2, \ldots, n$$$, respectively, then $$$0 \leq b_i \leq m$$$, $$$\sum_{i=1}^{n} b_i = k$$$ and the price per ticket on day $$$i$$$ will be $$$a_i + b_1 + b_2 + \ldots + b_{i-1} = a_i + \sum_{j=1}^{i-1} b_j$$$. Thus, the total cost will be:
$$$\sum_{i=1}^{n} (a_i + \sum_{j=1}^{i-1} b_j)b_i = \sum_{i=1}^{n} a_ib_i + \sum_{1 \leq j < i \leq n} b_ib_j$$$
Note that if we choose two days $$$i$$$, $$$j$$$ and swap $$$(a_i, b_i)$$$ with $$$(a_j, b_j)$$$, the above sum does not change its value. Therefore, we can freely rearrange the sequence $$$a$$$ without changing the answer. Let's sort the sequence $$$a$$$ in non-decreasing order. It is obvious that the first sum is minimized when we buy the $$$k$$$ cheapest tickets, i.e. $$$b = (m, m, \ldots, k \mod m, 0, 0, \ldots, 0)$$$. We will prove that the greedy strategy also minimizes the second sum, by noting that the second sum is equal to:
$$$\frac{1}{2} ((\sum_{i = 1}^{n}b_i)^{2} - \sum_{i = 1}^{n}{b_i^2}) = \frac{1}{2}k^2 - \frac{1}{2} \sum_{i = 1}^{n}{b_i^2}$$$
If there exists two days $$$i$$$, $$$j$$$ such that $$$0 < b_i \leq b_j < m$$$, then replacing $$$(b_i, b_j)$$$ with $$$(b_i - 1, b_j + 1)$$$ gives a smaller cost. Hence, the sequence $$$b = (m, m, \ldots, k \mod m, 0, 0, \ldots, 0)$$$ minimizes the overall cost.