Promo
Description
The store sells $n$ items, the price of the $i$-th item is $p_i$. The store's management is going to hold a promotion: if a customer purchases at least $x$ items, $y$ cheapest of them are free.
The management has not yet decided on the exact values of $x$ and $y$. Therefore, they ask you to process $q$ queries: for the given values of $x$ and $y$, determine the maximum total value of items received for free, if a customer makes one purchase.
Note that all queries are independent; they don't affect the store's stock.
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of items in the store and the number of queries, respectively.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^6$), where $p_i$ — the price of the $i$-th item.
The following $q$ lines contain two integers $x_i$ and $y_i$ each ($1 \le y_i \le x_i \le n$) — the values of the parameters $x$ and $y$ in the $i$-th query.
For each query, print a single integer — the maximum total value of items received for free for one purchase.
Input
The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of items in the store and the number of queries, respectively.
The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 10^6$), where $p_i$ — the price of the $i$-th item.
The following $q$ lines contain two integers $x_i$ and $y_i$ each ($1 \le y_i \le x_i \le n$) — the values of the parameters $x$ and $y$ in the $i$-th query.
Output
For each query, print a single integer — the maximum total value of items received for free for one purchase.
Samples
5 3
5 3 1 5 2
3 2
1 1
5 3
8
5
6
Note
In the first query, a customer can buy three items worth $5, 3, 5$, the two cheapest of them are $3 + 5 = 8$.
In the second query, a customer can buy two items worth $5$ and $5$, the cheapest of them is $5$.
In the third query, a customer has to buy all the items to receive the three cheapest of them for free; their total price is $1 + 2 + 3 = 6$.