A15256 | Promo

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.