В магазине поблизости продается \(n\) лопат. \(i\)-я лопата стоит \(a_i\) бурлей.
Миша хочет купить ровно \(k\) лопат. EКаждая лопата может быть куплена не более одного раза.
Миша может покупать лопаты в несколько покупок. В течение одной покупки он выбирает любое подмножество оставшихся (еще не купленных) лопат и покупает это подмножество.
Также в магазине есть \(m\) специальных предложений. \(j\)-е из них задано парой \((x_j, y_j)\) и означает, что если Миша купит ровно \(x_j\) лопат в течение одной покупки, то \(y_j\) самых дешевых из них он получит бесплатно (то есть он не будет платить за \(y_j\) самых дешевых лопат в течение текущей покупки).
Миша может использовать любое предложение любое (возможно, нулевое) количество раз, но он не может использовать более одного предложения в течение одной покупки (но он может покупать лопаты без использования каких-либо предложений).
Ваша задача — посчитать минимальную стоимость покупки \(k\) лопат, если Миша будет покупать их оптимальным образом.
Выходные данные
Выведите одно целое число — минимальную стоимость покупки \(k\) лопат, если Миша будет покупать их оптимальным образом.
Примечание
В первом тестовом примере Миша может купить лопаты на позициях \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1
|
7
|
|
2
|
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7
|
17
|
|
3
|
5 1 4
2 5 7 4 6
5 4
|
17
|