枫想要为巧克力和香草烤一些蛋糕。
有一天,她发现了 $$$n$$$ 神奇的蛋糕烤箱。第 $$$i$$$ 个烤箱每秒烘烤 $$$a_i$$$ 个蛋糕。蛋糕会留在各自的烤箱中,直到被收集为止。
在每一秒结束时,她可以传送到任何烤箱(包括她当前所在的烤箱)并收集该烤箱中迄今为止积累的所有蛋糕。
你的任务是确定 Maple 在 $$$m$$$ 秒内可以收集的最大蛋糕数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1\leq m\leq 10^8$$$) - 魔法烤箱的数量和 Maple 收集蛋糕的秒数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \le 10^5$$$) - 第 $$$i$$$ 个烤箱每秒烘烤的蛋糕数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示 Maple 在 $$$m$$$ 秒内可以收集的最大蛋糕数量。
示例
输入复制
33 41 2 33 21 2 31 1000100000
输出复制
20 8 100000000
注意
对于第一个测试用例,一个最佳解决方案如下:
- 在第一秒结束时,烤箱分别包含 $$$1$$$、$$$2$$$ 和 $$$3$$$ 蛋糕。枫传送到烤箱 $$$3$$$ 并收集所有 $$$3$$$ 蛋糕。烤箱 $$$3$$$ 现在剩余 $$$0$$$ 蛋糕。
- 在第二秒结束时,烤箱分别包含 $$$2$$$、$$$4$$$ 和 $$$3$$$ 蛋糕。枫传送到烤箱 $$$1$$$ 并收集所有 $$$2$$$ 蛋糕。烤箱 $$$1$$$ 现在还剩下 $$$0$$$ 蛋糕。
- 在第三秒结束时,烤箱分别包含 $$$1$$$、$$$6$$$ 和 $$$6$$$ 蛋糕。枫传送到烤箱 $$$2$$$ 并收集所有 $$$6$$$ 蛋糕。烤箱 $$$2$$$ 现在剩余 $$$0$$$ 蛋糕。
- 在第四秒结束时,烤箱分别包含 $$$2$$$、$$$2$$$ 和 $$$9$$$ 蛋糕。枫传送到烤箱 $$$3$$$ 并收集所有 $$$9$$$ 蛋糕。烤箱 $$$3$$$ 现在剩余 $$$0$$$ 蛋糕。
枫总共收集了$$$3+2+6+9=20$$$蛋糕。
对于第二个测试用例,一个最佳解决方案如下:
- 在第一秒结束时,烤箱分别包含 $$$1$$$、$$$2$$$ 和 $$$3$$$ 蛋糕。枫传送到烤箱 $$$2$$$ 并收集所有 $$$2$$$ 蛋糕。烤箱 $$$2$$$ 现在剩余 $$$0$$$ 蛋糕。
- 在第二秒结束时,烤箱分别包含 $$$2$$$、$$$2$$$ 和 $$$6$$$ 蛋糕。枫传送到烤箱 $$$3$$$ 并收集所有 $$$6$$$ 蛋糕。烤箱 $$$3$$$ 现在剩余 $$$0$$$ 蛋糕。
枫总共收集了$$$2+6=8$$$蛋糕。