CF1346C Spring Cleaning

塔尼娅想要整理她的书架。在书架上，有 $ n $ 个隔板，第 $ i $ 个隔板上放着 $ a_i $ 本书。塔尼娅希望每个隔板上的书本不超过 $ k $ 本。 为此，塔尼娅可以执行以下两种操作之一： 1. 选择一个书架上的隔板，将该隔板上的所有书都移到储藏室（即选择某个 $ i $ 并设 $ a_i := 0 $）。每执行一次该操作需要 $ x $ 秒。 2. 将所有书拿下来，重新均匀分配在 $ n $ 个隔板上。此操作也需要 $ y $ 秒。均匀分配意味着新数组 $ b $ 的总和等于 $ a $ 的总和，并且 $ \max(b) - \min(b) $ 的值尽可能小。 例如，如果数组 $ a = [5, 4, 3] $，均匀分配后的数组是 $ b = [4, 4, 4] $。如果 $ a = [1, 2, 3, 4] $，则可能均匀分配成 $ b = [2, 3, 3, 2] $ 或其任意顺序。 请你帮塔尼娅计算出，最少需要花多少秒，才能确保每个隔板上的书不超过 $ k $ 本。

输入第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示有 $ t $ 组测试用例。接下来是 $ t $ 组测试数据。 每组测试用例的第一行包含四个整数 $ n, k, x, y $（$ 1 \le k \le n \le 2 \cdot 10^5; 1 \le x, y \le 10^4 $），分别表示隔板的数目、每个隔板允许的最大书本数量、以及执行第一或第二种操作所需的时间。 每组测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $（$ 1 \le a_i \le n $），表示每个隔板上的书本数。 保证所有测试用例中，$ n $ 的总和不超过 $ 2 \cdot 10^5 $。

对于每个测试用例，输出一个行整数，表示塔尼娅为了满足每个隔板上的书不超过 $ k $ 本所需要的最少秒数。 **本翻译由 AI 自动生成**

In the first test case of the example, it's optimal to use the first operation on the fifth bookshelf. So the array $ a $ becomes $ [1, 2, 2, 3, 5] \rightarrow [1, 2, 2, 3, 0] $ . In the second test case of the example, it's optimal to use the first operation on the second bookshelf and then use the second operation. So the array $ a $ becomes $ [1, 5, 1, 5, 5] \rightarrow [1, 0, 1, 5, 5] \rightarrow [2, 2, 3, 3, 2] $ . In the third test case of the example, it's optimal to use the second operation. So the array $ a $ becomes $ [1, 2, 5, 3, 5] \rightarrow [4, 3, 3, 3, 3] $ . In the fourth test case of the example, it's optimal to use the first operation on the first and the second bookshelves. So the array $ a $ becomes $ [4, 4, 1, 1] \rightarrow [0, 0, 1, 1] $ . In the fifth test case of the example, it's optimal to use the second operation. So the array $ a $ becomes $ [4, 4, 1, 1] \rightarrow [2, 3, 2, 3] $ .