CF1697B Promo

一个商店正在出售 $ n $ 个物品，其中第 $ i $ 个物品价格为 $ p_i $ 。这个公司的老板想要进行一个优惠：如果一个客人购买了至少 $ x $ i个物品，其中最便宜的 $ y $ 个就会免费。 但是，这个老板还没有决定 $ x $ 和 $ y $ 的大小。所以，他问了你 $ q $ 种情况: 对于每个 $ x $ 和 $ y $ ，告诉他在这种情况下，如果一个顾客进行了一次购买，则他最多可以省下多少钱（指免费商品的总价值）？ 注意：每种情况不互相影响（他们不影响商店的储货）。

第一行包含两个整数 $ 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 $ 的大小。

对于每种情况，输出一个整数，代表在这种情况下顾客最多可以~~白嫖~~省下的钱。 ## 样例解释 在第一种情况中，这个顾客可以购买三个价值为 $ 5, 3, 5$ 的物品，其中两个最便宜的价值为 $ 3 + 5 = 8 $ 。 在第二种情况中，这个顾客可以购买两个物品，价值为 $ 5 $ 和 $ 5 $ , 其中最便宜的为 $ 5 $ 。 在第三种情况中，这个顾客得购买所有物品来省下最便宜三个物品的钱： $ 1 + 2 + 3 = 6 $ 。

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