{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e附近商店有$$$n$$$把铲子。第$$$i$$$把铲子的价格是$$$a_i$$$博尔。\u003c/p\u003e\u003cp\u003eMisha必须购买\u003cspan class\u003d\"tex-font-style-bf\"\u003e确切地\u003c/span\u003e$$$k$$$把铲子。每把铲子只能购买\u003cspan class\u003d\"tex-font-style-bf\"\u003e不超过一次\u003c/span\u003e。\u003c/p\u003e\u003cp\u003eMisha可以通过多次购买来购买铲子。在一次购买中,他可以选择剩余的(未购买的)铲子的任意子集并购买该子集。\u003c/p\u003e\u003cp\u003e商店还有$$$m$$$个特别优惠。第$$$j$$$个优惠以一对$$$(x_j, y_j)$$$的形式给出,意味着如果Misha在\u003cspan class\u003d\"tex-font-style-bf\"\u003e一次购买中确切地\u003c/span\u003e购买$$$x_j$$$把铲子,则其中$$$y_j$$$ \u003cspan class\u003d\"tex-font-style-bf\"\u003e最便宜的\u003c/span\u003e铲子是免费的(即在当前购买中他不会为$$$y_j$$$最便宜的铲子付费)。\u003c/p\u003e\u003cp\u003eMisha可以任意次数地使用任何优惠,但他不能在\u003cspan class\u003d\"tex-font-style-bf\"\u003e一次购买中使用多个\u003c/span\u003e优惠(但他可以购买铲子而不使用任何优惠)。\u003c/p\u003e\u003cp\u003e你的任务是计算Misha在最佳情况下购买$$$k$$$把铲子的最低成本。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含三个整数$$$n, m$$$和$$$k$$$($$$1 \\le n, m \\le 2 \\cdot 10^5, 1 \\le k \\le min(n, 2000)$$$)—商店中的铲子数量、特别优惠数量和Misha必须购买的铲子数量。\u003c/p\u003e\u003cp\u003e输入的第二行包含$$$n$$$个整数$$$a_1, a_2, \\dots, a_n$$$($$$1 \\le a_i \\le 2 \\cdot 10^5$$$),其中$$$a_i$$$是第$$$i$$$把铲子的价格。\u003c/p\u003e\u003cp\u003e接下来的$$$m$$$行包含特别优惠。第$$$j$$$个特别优惠以一对整数$$$(x_i, y_i)$$$($$$1 \\le y_i \\le x_i \\le n$$$)的形式给出,表示如果Misha在某次购买中确切地购买$$$x_i$$$把铲子,则他可以免费获得其中$$$y_i$$$最便宜的。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数—如果Misha以最佳方式购买$$$k$$$把铲子,则购买的最低成本。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 4 5\n2 5 4 2 6 3 1\n2 1\n6 5\n2 1\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9 4 8\n6 8 5 1 8 1 1 2 1\n9 2\n8 4\n5 3\n9 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 1 4\n2 5 7 4 6\n5 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e17\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,Misha可以在第一次购买中购买位置为$$$1$$$和$$$4$$$的铲子(价格均为$$$2$$$),并使用第一个或第三个特别优惠中的一个免费获得其中一个。然后他可以在第二次购买中购买位置为$$$3$$$和$$$6$$$的铲子(价格分别为$$$4$$$和$$$3$$$),并使用第一个或第三个特别优惠中的一个免费获得第二个。然后他可以购买价格为$$$1$$$的位置为$$$7$$$的铲子。因此总成本为$$$4 + 2 + 1 \u003d 7$$$。\u003c/p\u003e\u003cp\u003e在第二个示例中,Misha可以购买位置为$$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$和$$$8$$$的铲子(价格分别为$$$6$$$、$$$8$$$、$$$5$$$、$$$1$$$和$$$2$$$),并免费获得其中三个最便宜的(价格为$$$5$$$、$$$1$$$和$$$2$$$)。然后他可以购买价格均为$$$1$$$的位置为$$$6$$$、$$$7$$$和$$$9$$$的铲子,而不使用任何特别优惠。因此总成本为$$$6 + 8 + 1 + 1 + 1 \u003d 17$$$。\u003c/p\u003e\u003cp\u003e在第三个示例中,Misha可以购买四把最便宜的铲子,而不使用任何特别优惠,总成本为$$$17$$$。\u003c/p\u003e"}}]}