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 自动生成