B. Промоакция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В магазине продаются $$$n$$$ товаров, цена $$$i$$$-го товара равна $$$p_i$$$. Руководство магазина собирается провести акцию: если в чеке не менее $$$x$$$ товаров, $$$y$$$ самых дешевых из них будут проданы бесплатно.

Руководство ещё не определилось с точными значениями $$$x$$$ и $$$y$$$. Поэтому они просят вас обработать $$$q$$$ запросов: для заданных значений $$$x$$$ и $$$y$$$ определить максимальную суммарную стоимость товаров, которые клиент может получить бесплатно, совершив одну покупку.

Обратите внимание, что запросы являются независимыми, т. е. они никак не влияют на ассортимент магазина.

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — количество товаров в магазине и количество запросов, соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^6$$$), где $$$p_i$$$ — цена $$$i$$$-го товара.

Следующие $$$q$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le y_i \le x_i \le n$$$) — значения параметров $$$x$$$ и $$$y$$$ в $$$i$$$-м запросе.

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

Для каждого запроса выведите одно целое число — максимальная суммарная стоимость товаров, которые можно получить бесплатно за одну покупку (один чек).

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

В первом запросе из примера можно купить три товара стоимостью $$$5, 3, 5$$$, два самых дешевых из них имеют стоимость $$$3 + 5 = 8$$$.

Во втором запросе можно купить два товара стоимостью $$$5$$$ и $$$5$$$, самый дешевый из них имеет стоимость $$$5$$$.

В третьем запросе необходимо купить все товары для участия в акции, три самых дешевых из них имеют стоимость $$$1 + 2 + 3 = 6$$$.