Shovels Shop

题意翻译

## Description 商店里有 $n$ 双鞋，每双鞋都有一个价格。你要买其中的严格 $k$ 双。每双鞋只能被买一次。 你每次购买可以挑选剩余鞋中的任意一个子集来购买集合中所有的鞋。 有 $m$ 种套餐，第 $i$ 种套餐代表如果一次性购买 $x_i$ 双鞋则其中最便宜的 $y_i$ 双免费。 这 $m$ 种套餐每种都可以用任意次。 现在请求出买严格 $k$ 双鞋的最小化费。 ## Input 第一行是三个整数 $n,~m,~k$ 一行 $n$ 个整数描述每双鞋的价格 下面 $m$ 行，每行两个整数 $x_i,~y_i$，描述一个套餐。 ## Output 输出一行一个整数代表答案。 ## Limitation $1~\leq~n,~m\leq~2~\times~10^5$ $1~\leq~k~\leq~\min(n, 2000)$ $1~\leq~a_i~\leq~2~\times~10^5$ Translated By @ 一扶苏一

题目描述

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

7

输入样例 #2

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

输出样例 #2

17

输入样例 #3

5 1 4
2 5 7 4 6
5 4

输出样例 #3

17

说明

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