该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem G. Go Shopping! Target Tilenn's Shop!

Input file:　standard input
Output file:　standard output
Time limit:　1 second
Memory limit:　256 megabytes

杰神非常好客，也许是这样的。因而，杰神有一家超市，应该是很合理的。

Ocean 知道杰神超市里面有 $n$ 件商品，应该也是很合理的。

那么，现在 Ocean 有 $q$ 个问题。他想问问你：

如果杰神想要让 Ocean 挑选最多 $k$ 个价值不大于 $x$ 的商品，Ocean 能挑选的价值和最大为多少呢？

Input

第一行包含两个整数 $n$ $(1 \leq n \leq 10^5)$, $q$ $(1 \leq q \leq 10^5)$，代表商品的总数以及询问的次数。

第二行包含 $n$ 个数字，代表商品价格 $a_i$ $(1 \leq a_i \leq 10^9)$。

接下来总共有 $q$ 行，每行包含两个正整数 $k$ $(1 \leq k \leq n)$ , $x$ $(1 \leq x \leq 10^9)$。

Output

包含 $q$ 行，每行包含一个整数，代表每个询问的答案。

Example