题目描述

一个商店正在出售 $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$ 。

样例

5 3
5 3 1 5 2
3 2
1 1
5 3

8
5
6