You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

收集蛋糕

菜鸡学姐 想给 wy 和 kirep 烤一些蛋糕。

一天，她发现了n 台魔法蛋糕烤箱。第 i 台烤箱每秒能烤出aᵢ个蛋糕。蛋糕会一直留在各自的烤箱里，直到被收集。

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

你的任务是确定 菜鸡学姐 在m 秒内最多能收集到多少个蛋糕。

输入

每个测试包含多组测试用例。第一行输入测试用例的数量t（1≤t≤1000）。接下来是各测试用例的描述。

每组测试用例的第一行包含两个整数n和m（1≤n≤10⁵，1≤m≤10⁸）—— 分别表示魔法烤箱的数量和 菜鸡学姐 收集蛋糕的总时长（秒数）。

第二行包含n 个整数a₁, a₂, …, aₙ（1≤aᵢ≤10⁵）—— 表示第 i 台烤箱每秒烤出的蛋糕数量。

题目保证所有测试用例中 n 的总和不超过 2×10⁵。

输出

对于每组测试用例，输出一个整数，表示 菜鸡学姐 在 m 秒内最多能收集到的蛋糕数量。

示例

输入

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

输出

20
8
100000000