В магазине продаются \(n\) товаров, цена \(i\)-го товара равна \(p_i\). Руководство магазина собирается провести акцию: если в чеке не менее \(x\) товаров, \(y\) самых дешевых из них будут проданы бесплатно.
Руководство ещё не определилось с точными значениями \(x\) и \(y\). Поэтому они просят вас обработать \(q\) запросов: для заданных значений \(x\) и \(y\) определить максимальную суммарную стоимость товаров, которые клиент может получить бесплатно, совершив одну покупку.
Обратите внимание, что запросы являются независимыми, т. е. они никак не влияют на ассортимент магазина.
Выходные данные
Для каждого запроса выведите одно целое число — максимальная суммарная стоимость товаров, которые можно получить бесплатно за одну покупку (один чек).
Примечание
В первом запросе из примера можно купить три товара стоимостью \(5, 3, 5\), два самых дешевых из них имеют стоимость \(3 + 5 = 8\).
Во втором запросе можно купить два товара стоимостью \(5\) и \(5\), самый дешевый из них имеет стоимость \(5\).
В третьем запросе необходимо купить все товары для участия в акции, три самых дешевых из них имеют стоимость \(1 + 2 + 3 = 6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
5 3 1 5 2
3 2
1 1
5 3
|
8
5
6
|