A12473 · Shovels Shop

题目描述

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.

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.

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

输入 #1

7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1

输出 #1

输入 #2

9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7

输出 #2

输入 #3

5 1 4
2 5 7 4 6
5 4

输出 #3