商店里共有n件商品在售卖，它们的价格分别为p1,p2,p3,……,pn，店主准备进行如下的促销活动：如果顾客在商店里购买了不少于x（购买商品数量>=x）件商品，则其中价格最便宜的y件商品可以免费。

店主现在还没有确定x和y的值。因此，他向我们发出了q次询问：对于给定的x和y，请帮店主算出免费商品的价格之和最多是多少？

特别提醒，每次询问都是独立的，不会影响商店中的商品数量，即不会影响下一次询问的结果。

第一行共有两个整数n和q(1≤n, q≤2*10⁵)：分别为商品的数量和询问的次数。

第二行共有n个整数p1,p2,……,pn (1≤pi≤10⁶)，分别为n件商品的价格，pi为第i件商品的价格；

接下来共有q行，分别对应q次询问。每行两个整数：xi和yi（1≤yi≤xi≤n），分别为第i次询问顾客购买的商品总数x和可以免费的商品数量y；

输出共q行。对于每次询问，输出一行一个整数：顾客可以得到的免费商品价格之和的最大值。