U516404 购物 --前缀和[普及-]

小 $A$ 家附近的超市在进行大促销! 超市中有 $n$ 种不同的商品，第 $i$ 件商品的价格为 $a_i$。促销规则如下：如果客户在超市中买了至少 $x$ 件物品，那么其中最便宜的 $y$ 件物品将免费。 该活动一共进行 $q$ 天，每天超市会给出当天的 $x$ 和 $y$ 的值。小 $A$ 想要知道每一天他能获得的免费商品的最大价值。为了满足多样性，他在同一天内不会买相同的商品，但不同天内可以购买相同的商品。

第一行输人两个整数 $n$ 和 $q$，分别表示商品的个数和活动持续的天数。 接下来的一行包含 $n$ 个正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 件商品的价格。 接下来 $q$ 行，每一行包含两个整数 $x_i,y_i$。

输出 $q$ 行表示每一天能获得的免费商品的最大价值。

#### 数据范围 对于所有数据 $1\le n\le 2\times 10^5,1\le q\le 2\times 10^5,1\le a_i\le 10^6, 1\le y_i\le x_i \le n$。 |测试点编号|特殊限制| |-|-| |$1\sim 2$|$n,q\le 10$| |$3\sim 10$|无特殊限制|