B. 蛋糕收集

每次测试的时间限制：1 秒
每次测试的内存限制：512 兆字节

枫想要为巧克力与香草烤一些蛋糕。

一天，她发现了 $n$ 个神奇的蛋糕烤炉。第 $i$ 个烤炉每秒钟烤出 $a_i$ 个蛋糕。
蛋糕会一直留在各自的烤炉中，直到被收集。

在每一秒结束时，她可以传送到任意一个烤炉（包括她当前所在的烤炉），并收集那个烤炉中到当时为止积累的所有蛋糕。

你的任务是确定在 $m$ 秒内，枫最多可以收集多少个蛋糕。

---

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。
接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 10^5$，$1 \le m \le 10^8$）—— 魔法烤炉的数量，以及枫收集蛋糕的秒数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^5$）—— 第 $i$ 个烤炉每秒钟烤出的蛋糕数量。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

---

输出

对于每个测试用例，输出一个整数，表示在 $m$ 秒内枫能收集到的最大蛋糕数量。

---

示例

输入

3
3 4
1 2 3
3 2
1 2 3
1 1000
100000

输出

20
8
100000000

---

提示

对于第一个测试用例，一种最优方案如下：

1. 第一秒结束时，烤炉中的蛋糕数分别为 $1$、$2$、$3$。枫传送到烤炉 $3$，收集 $3$ 个蛋糕。烤炉 $3$ 现在剩余 $0$ 个蛋糕。
2. 第二秒结束时，烤炉中的蛋糕数分别为 $2$、$4$、$3$。枫传送到烤炉 $1$，收集 $2$ 个蛋糕。烤炉 $1$ 现在剩余 $0$ 个蛋糕。
3. 第三秒结束时，烤炉中的蛋糕数分别为 $1$、$6$、$6$。枫传送到烤炉 $2$，收集 $6$ 个蛋糕。烤炉 $2$ 现在剩余 $0$ 个蛋糕。
4. 第四秒结束时，烤炉中的蛋糕数分别为 $2$、$2$、$9$。枫传送到烤炉 $3$，收集 $9$ 个蛋糕。烤炉 $3$ 现在剩余 $0$ 个蛋糕。

总共收集到的蛋糕数为：

[ 3 + 2 + 6 + 9 = 20 ]

对于第二个测试用例，一种最优方案如下：

1. 第一秒结束时，烤炉中的蛋糕数分别为 $1$、$2$、$3$。枫传送到烤炉 $2$，收集 $2$ 个蛋糕。烤炉 $2$ 现在剩余 $0$ 个蛋糕。
2. 第二秒结束时，烤炉中的蛋糕数分别为 $2$、$2$、$6$。枫传送到烤炉 $3$，收集 $6$ 个蛋糕。烤炉 $3$ 现在剩余 $0$ 个蛋糕。

总共收集到的蛋糕数为：

[ 2 + 6 = 8 ]