Tanya 想要整理她的书柜。书柜里有$$$n$$$个书架,第$$$i$$$个书架上放着$$$a_i$$$本书。如果每个书架上的书不超过 $$$k$$$ ,Tanya 就会感到满意。
Tanya 可以执行以下两个操作之一来实现她的目标:
1. 选择一个书架并将其中的所有书籍放入储藏室(即选择一些 $$$i$$$ 并分配 $$$a_i := 0$$$)。在此操作期间,她花费了 $$$x$$$ 秒。
2. 从所有 $$$n$$$ 书架中取出所有书籍,并将它们均匀地分布在所有 $$$n$$$ 书架之间(该术语的定义如下)。在此操作期间,她花费了 $$$y$$$ 秒。
考虑 $$$n$$$ 整数的序列 $$$a$$$。那么它的均匀分布就是 $$$n$$$ 整数的序列 $$$b$$$,$$$b$$$ 的总和等于 $$$a$$$ 的总和,并且值 $$$max(b) - min(b)$$$ 是可能的最小值。
例如,如果数组 $$$a=[5, 4, 3]$$$,则其均匀分布为 $$$b=[4, 4, 4]$$$。如果 $$$a=[1, 2, 3, 4]$$$ 则其均匀分布为 $$$b=[2, 3, 3, 2]$$$ (或该数组的任何排列)。
你的任务是找出 Tanya 获得每个书架上不超过 $$$k$$$ 本书的书柜所需的最少秒数。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含四个整数 $$$n、k、x$$$ 和 $$$y$$$ ($$$1 \le k \le n \le 2 \cdot 10^5; 1 \le x, y \le 10^4$$$) - 书架数量、每个书架上所需的最大书籍数量以及 Tanya 在第一和第二个时间段花费的秒数分别进行第二次操作。
测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 书架上的书籍数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。
输出
对于每个测试用例,打印答案 - Tanya 获取每个书架上不超过 $$$k$$$ 本书的书柜所需的最短秒数。
示例
输入 #1
6 5 4 3 5 1 2 2 3 5 5 3 4 5 1 5 1 5 5 5 4 5 6 1 2 5 3 5 4 3 2 10 4 4 1 1 4 3 10 2 4 4 1 1 4 1 5 4 1 2 1 3
输出 #1
3 9 6 4 2 9
注意
在示例的第一个测试用例中,最好在第五个书架上使用第一个操作。因此数组 $$$a$$$ 变为 $$$[1, 2, 2, 3, 5] \rightarrow [1, 2, 2, 3, 0]$$$。
在示例的第二个测试用例中,最佳做法是在第二个书架上使用第一个操作,然后使用第二个操作。因此数组 $$$a$$$ 变为 $$$[1, 5, 1, 5, 5] \rightarrow [1, 0, 1, 5, 5] \rightarrow [2, 2, 3, 3, 2]$$$。
在示例的第三个测试用例中,最好使用第二个操作。因此数组 $$$a$$$ 变为 $$$[1, 2, 5, 3, 5] \rightarrow [4, 3, 3, 3, 3]$$$。
在示例的第四个测试用例中,最好在第一个和第二个书架上使用第一个操作。因此数组 $$$a$$$ 变为 $$$[4, 4, 1, 1] \rightarrow [0, 0, 1, 1]$$$。
在示例的第五个测试用例中,最好使用第二个操作。因此数组 $$$a$$$ 变为 $$$[4, 4, 1, 1] \rightarrow [2, 3, 2, 3]$$$。