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

附近商店里有 $n$ 把铲子。第 $i$ 把铲子的价格为 $a_i$ 卢布。

米沙必须恰好购买 $k$ 把铲子，且每把铲子最多只能购买一次。

米沙可以分多次进行购买。在每次购买中，他可以从当前剩余（尚未购买）的铲子中任选一个子集，并买下该子集中的全部铲子。

此外，商店还提供 $m$ 种特价优惠。其中第 $j$ 种优惠以数对 $(x_j, y_j)$ 给出，表示：若米沙在某次购买中恰好购买 $x_j$ 把铲子，则此次购买中价格最低的 $y_j$ 把铲子将免费（即本次购买中，这 $y_j$ 把最便宜的铲子无需付费）。

米沙可以任意多次（包括零次）使用任意一种优惠，但在同一次购买中至多只能使用一种优惠（当然，他也可以选择在某次购买中不使用任何优惠）。

你的任务是：在最优购买策略下，计算购买 $k$ 把铲子所需的最小总花费。

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.

输入的第一行包含三个整数 $n, m$ 和 $k$（$1 \le n, m \le 2 \cdot 10^5$，$1 \le k \le \min(n, 2000)$），分别表示商店中铲子的数量、特价优惠的数量，以及米沙需要购买的铲子数量。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^5$），其中 $a_i$ 表示第 $i$ 把铲子的价格。

接下来的 $m$ 行描述特价优惠。第 $j$ 个优惠以一对整数 $(x_i, y_i)$（$1 \le y_i \le x_i \le n$）给出，表示：若米沙在某次购买中恰好买下 $x_i$ 把铲子，则他可以免费获得其中最便宜的 $y_i$ 把。

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

输出一个整数——如果米沙以最优方式购买 $k$ 把铲子，所需的最低成本。

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

在第一个例子中，米沙可以在第一次购买时购买位置 $1$ 和 $4$ 上的铲子（价格均为 $2$），并利用第一个或第三个特价优惠，免费获得其中一把。接着，他可以在第二次购买时购买位置 $3$ 和 $6$ 上的铲子（价格分别为 $4$ 和 $3$），并利用第一个或第三个特价优惠，免费获得其中一把（即价格为 $3$ 的那把）。然后，他可以单独购买位置 $7$ 上价格为 $1$ 的铲子。因此总花费为 $4 + 2 + 1 = 7$。

在第二个例子中，米沙可以一次性购买位置 $1$、$2$、$3$、$4$ 和 $8$ 上的铲子（价格分别为 $6$、$8$、$5$、$1$ 和 $2$），并免费获得其中最便宜的三把（价格分别为 $5$、$1$ 和 $2$）。接着，他可以再购买位置 $6$、$7$ 和 $9$ 上的铲子（价格均为 $1$），且不使用任何特价优惠。因此总花费为 $6 + 8 + 1 + 1 + 1 = 17$。

在第三个例子中，米沙可以在不使用任何特价优惠的情况下，直接购买最便宜的四把铲子，总花费为 $17$。