CF1697B.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.

商店出售 $n$ 种商品，第 $i$ 种商品的价格为 $p_i$。商店管理层计划开展一项促销活动：若顾客一次购买至少 $x$ 件商品，则其中最便宜的 $y$ 件免费。

目前管理层尚未确定 $x$ 和 $y$ 的具体取值。因此，他们请你处理 $q$ 个查询：对每个给定的 $x$ 和 $y$，求出顾客一次购物所能获得的免费商品总价值的最大值。

注意：所有查询相互独立，不会影响商店的库存。

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.

第一行包含两个整数 $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$）—— 表示第 $i$ 次查询中的参数 $x$ 和 $y$ 的值。

For each query, print a single integer — the maximum total value of items received for free for one purchase.

对于每个查询，输出一个整数——一次购买中可免费获得的物品的总价值的最大值。

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$.

在第一次查询中，顾客可以购买三件价格分别为 $5$、$3$、$5$ 的商品，其中最便宜的两件价格之和为 $3 + 5 = 8$。

在第二次查询中，顾客可以购买两件价格均为 $5$ 的商品，其中最便宜的一件价格为 $5$。

在第三次查询中，顾客必须购买所有商品，才能免费获得其中最便宜的三件；这三件商品的总价为 $1 + 2 + 3 = 6$。