附近的商店里有 $$$n$$$ 铲子。第 $$$i$$$ 铲子花费 $$$a_i$$$ 布尔。
Misha 必须购买 $$$k$$$ 铲子。每把铲子只能购买一次。
米莎可以通过多次购买来购买铲子。在一次购买期间,他可以选择剩余(未购买)铲子的任何子集并购买该子集。
商店里还有$$$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$$$ 行包含特别优惠。其中第 $$$j$$$ 是以一对整数 $$$(x_i, y_i)$$$ ($$$1 \le y_i \le x_i \le n$$$) 形式给出的,这意味着如果 Misha 在一次购买过程中恰好购买了 $$$x_i$$$ 铲子,那么他可以免费拿走其中最便宜的 $$$y_i$$$。
输出
打印一个整数 — 如果 Misha 以最佳方式购买 $$$k$$$ 铲子,则购买它们的最低成本。
示例
输入 #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
注意
在第一个示例中,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$$$。