尽管海伦（Helen）是一家知名公司的高薪工程师，但她非常喜欢省钱！这一次，她想弄清楚如何利用附近杂货店的促销活动来优化她的购物。

每次海伦光顾这家商店时，她都会恰好购买 $n$ 件商品。第 $i$ 件商品的价格为 $c_i$ 卢布（burles）。在第 $j$ 天，商店提供以下促销活动：每购买 $x_j$ 件商品，你只需支付该组中价格最低的商品原价的 $y_j$ 倍。这意味着海伦可以通过将她的 $n$ 件商品分成大小为 $x_j$ 的组（以及可能一个大小小于 $x_j$ 的组），并对每个大小为 $x_j$ 的组中价格最低的一件商品支付较少的费用（即原价的 $y_j$ 倍）来省钱；如果存在那个较小的组，则该组中的商品无法享受此优惠。

商店已经公布了接下来 $m$ 天的促销活动。请帮助海伦计算在这些天里，她每天购买所有 $n$ 件商品所需的最小金额。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ （$1 \le n, m \le 300\,000$），分别表示海伦每次光顾商店时购买的商品数量以及需要考虑的促销天数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ （$1 \le c_i \le 10^9$），表示每件商品的费用。

接下来有 $m$ 行。其中的第 $j$ 行包含一个整数 $x_j$ 和一个实数 $y_j$ （$2 \le x_j \le 300\,000$，$0 \le y_j \le 1$）—— 表示第 $j$ 天促销活动的参数。实数 $y_j$ 的小数点后最多有六位数字。

输出格式

输出 $m$ 个实数。其中第 $i$ 个数应该等于在第 $i$ 天购买所有 $n$ 件商品所需的最小可能金额。如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则将被视为正确。

样例

输入样例 1

4 2
1 1 1 1
2 0.75
3 0

输出样例 1

3.5000000000
3.0000000000

输入样例 2

3 3
10 9 2
2 0.5
3 0.2
4 0

输出样例 2

16.5000000000
19.4000000000
21.0000000000