CF1154F Shovels Shop

附近的商店里有 $n$ 把铁锹，第 $i$ 把铁锹的价格为 $a_i$ 布尔。 Misha 需要恰好买 $k$ 把铁锹。每把铁锹最多只能买一次。 Misha 可以分多次购买铁锹。每次购买时，他可以从剩下的（未购买的）铁锹中任选一个子集购买。 商店里还有 $m$ 个特殊优惠。第 $j$ 个优惠用一对数 $(x_j, y_j)$ 表示，意思是如果 Misha 在一次购买中恰好买了 $x_j$ 把铁锹，那么其中价格最便宜的 $y_j$ 把铁锹可以免费获得（即本次购买中最便宜的 $y_j$ 把铁锹不需要付钱）。 Misha 可以任意次数（包括零次）使用任意优惠，但每次购买最多只能使用一个优惠（当然也可以不使用任何优惠）。 你的任务是计算，若 Misha 以最优方式购买 $k$ 把铁锹，所需支付的最小总费用。

输入的第一行包含三个整数 $n, m, k$（$1 \le n, m \le 2 \cdot 10^5, 1 \le k \le \min(n, 2000)$），分别表示商店中铁锹的数量、特殊优惠的数量，以及 Misha 需要购买的铁锹数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^5$），其中 $a_i$ 表示第 $i$ 把铁锹的价格。 接下来的 $m$ 行，每行包含一对整数 $(x_i, y_i)$（$1 \le y_i \le x_i \le n$），表示一个特殊优惠：如果 Misha 在一次购买中恰好买了 $x_i$ 把铁锹，那么其中价格最便宜的 $y_i$ 把铁锹可以免费获得。

输出一个整数，表示以最优方式购买 $k$ 把铁锹所需支付的最小总费用。

在第一个样例中，Misha 可以在第一次购买时买第 $1$ 和第 $4$ 把铁锹（价格均为 $2$），使用第一个或第三个优惠获得其中一把免费。然后第二次购买第 $3$ 和第 $6$ 把铁锹（价格分别为 $4$ 和 $3$），再次使用第一个或第三个优惠获得其中一把免费。最后再买第 $7$ 把铁锹（价格为 $1$）。因此总费用为 $4 + 2 + 1 = 7$。 在第二个样例中，Misha 可以在第一次购买时买第 $1$、$2$、$3$、$4$ 和 $8$ 把铁锹（价格分别为 $6$、$8$、$5$、$1$ 和 $2$），获得其中最便宜的三把（价格为 $5$、$1$ 和 $2$）免费。然后再买第 $6$、$7$ 和 $9$ 把铁锹（价格均为 $1$），不使用任何优惠。总费用为 $6 + 8 + 1 + 1 + 1 = 17$。 在第三个样例中，Misha 可以直接买最便宜的四把铁锹，不使用任何优惠，总费用为 $17$。 由 ChatGPT 4.1 翻译