Shovels Shop
Contest: Codeforces Round 552 (Div. 3)
Difficulty rating: 2100
Tags: dp, greedy, sortings

There are $$$n$$$ shovels in the nearby shop. The $$$i$$$-th shovel costs $$$a_i$$$ bourles.

Misha has to buy exactly $$$k$$$ shovels. Each shovel can be bought no more than once.

Misha can buy shovels by several purchases. During one purchase he can choose any subset of remaining (non-bought) shovels and buy this subset.

There are also $$$m$$$ special offers in the shop. The $$$j$$$-th of them is given as a pair $$$(x_j, y_j)$$$, and it means that if Misha buys exactly $$$x_j$$$ shovels during one purchase then $$$y_j$$$ most cheapest of them are for free (i.e. he will not pay for $$$y_j$$$ most cheapest shovels during the current purchase).

Misha can use any offer any (possibly, zero) number of times, but he cannot use more than one offer during one purchase (but he can buy shovels without using any offers).

Your task is to calculate the minimum cost of buying $$$k$$$ shovels, if Misha buys them optimally.

Input format:
The first line of the input contains three integers $$$n, m$$$ and $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5, 1 \le k \le min(n, 2000)$$$) — the number of shovels in the shop, the number of special offers and the number of shovels Misha has to buy, correspondingly.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the cost of the $$$i$$$-th shovel.

The next $$$m$$$ lines contain special offers. The $$$j$$$-th of them is given as a pair of integers $$$(x_i, y_i)$$$ ($$$1 \le y_i \le x_i \le n$$$) and means that if Misha buys exactly $$$x_i$$$ shovels during some purchase, then he can take $$$y_i$$$ most cheapest of them for free.

Output format:
Print one integer — the minimum cost of buying $$$k$$$ shovels if Misha buys them optimally.

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

Note:
In the first example Misha can buy shovels on positions $$$1$$$ and $$$4$$$ (both with costs $$$2$$$) during the first purchase and get one of them for free using the first or the third special offer. And then he can buy shovels on positions $$$3$$$ and $$$6$$$ (with costs $$$4$$$ and $$$3$$$) during the second purchase and get the second one for free using the first or the third special offer. Then he can buy the shovel on a position $$$7$$$ with cost $$$1$$$. So the total cost is $$$4 + 2 + 1 = 7$$$.

In the second example Misha can buy shovels on positions $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ and $$$8$$$ (costs are $$$6$$$, $$$8$$$, $$$5$$$, $$$1$$$ and $$$2$$$) and get three cheapest (with costs $$$5$$$, $$$1$$$ and $$$2$$$) for free. And then he can buy shovels on positions $$$6$$$, $$$7$$$ and $$$9$$$ (all with costs $$$1$$$) without using any special offers. So the total cost is $$$6 + 8 + 1 + 1 + 1 = 17$$$.

In the third example Misha can buy four cheapest shovels without using any special offers and get the total cost $$$17$$$.

Example input:
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1

Example output:
7

Example input:
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7

Example output:
17

Editorial:
First of all, since we are going to buy exactly $$$k$$$ shovels, we may discard $$$n - k$$$ most expensive shovels from the input and set $$$n = k$$$ (and solve the problem which requires us to buy all the shovels). Also, let's add an offer which allows us to buy $$$1$$$ shovel and get $$$0$$$ cheapest of them for free, to simulate that we can buy shovels without using offers.
Now we claim that if we sort all the shovels by their costs, it's optimal to divide the array of costs into some consecutive subarrays and buy each subarray using some offer. Why should the sets of shovels for all purchases be consecutive subarrays? Suppose it's not so: let's pick two purchases such that they are "mixed" in the array of costs, i. e. there exists at least one shovel $$$A$$$ bought in the first purchase such that there exists a shovel $$$B$$$ cheaper than it and a shovel $$$C$$$ more expensive than it, both bought in the second purchase. If shovel $$$A$$$ is for free, then we may "swap" shovels $$$A$$$ and $$$C$$$, otherwise we may swap shovels $$$A$$$ and $$$B$$$, and the answer won't become worse. So, we can do it until all purchases correspond to subsegments in the array of costs.
Then it's easy to see that we can make purchases in such a way that we always buy some amount of cheapest shovels. And now the problem can be solved by knapsack-like dynamic programming: let $$$dp_i$$$ be the minimum cost to buy exactly $$$i$$$ cheapest shovels. $$$dp_0$$$ is $$$0$$$, and for each offer $$$(x, y)$$$ we can update $$$dp_{i + x}$$$ by the value of $$$dp_i + sum(i + y + 1, i + x)$$$, where $$$sum(l, r)$$$ is the sum of costs of all shovels in the sorted order from shovel on position $$$l$$$ to shovel on position $$$r$$$, inclusive (these sums can be calculated in $$$O(1)$$$ using partial sums method).