F. Магазин лопат
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В магазине поблизости продается $$$n$$$ лопат. $$$i$$$-я лопата стоит $$$a_i$$$ бурлей.

Миша хочет купить ровно $$$k$$$ лопат. EКаждая лопата может быть куплена не более одного раза.

Миша может покупать лопаты в несколько покупок. В течение одной покупки он выбирает любое подмножество оставшихся (еще не купленных) лопат и покупает это подмножество.

Также в магазине есть $$$m$$$ специальных предложений. $$$j$$$-е из них задано парой $$$(x_j, y_j)$$$ и означает, что если Миша купит ровно $$$x_j$$$ лопат в течение одной покупки, то $$$y_j$$$ самых дешевых из них он получит бесплатно (то есть он не будет платить за $$$y_j$$$ самых дешевых лопат в течение текущей покупки).

Миша может использовать любое предложение любое (возможно, нулевое) количество раз, но он не может использовать более одного предложения в течение одной покупки (но он может покупать лопаты без использования каких-либо предложений).

Ваша задача — посчитать минимальную стоимость покупки $$$k$$$ лопат, если Миша будет покупать их оптимальным образом.

Входные данные

Первая строка входных данных содержит три целых числа $$$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$$$ самых дешевых из них бесплатно.

Выходные данные

Выведите одно целое число — минимальную стоимость покупки $$$k$$$ лопат, если Миша будет покупать их оптимальным образом.

Примеры
Входные данные
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1
Выходные данные
7
Входные данные
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7
Выходные данные
17
Входные данные
5 1 4
2 5 7 4 6
5 4
Выходные данные
17
Примечание

В первом тестовом примере Миша может купить лопаты на позициях $$$1$$$ и $$$4$$$ (обе со стоимостями $$$2$$$) в течение первой покупки и получить одну из них бесплатно при помощи первого или третьего специального предложения. И затем он может купить лопаты на позициях $$$3$$$ и $$$6$$$ (со стоимостями $$$4$$$ и $$$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$$$.