Bear and Contribution

来源:FlierKing大佬的PPT 有 $n$ 个贡献值 $v_1$ , $v_2$ ,…, $v_n$ ，将其中一个贡献值 $+5$ 需要花费 $b$ ，将其中一个贡献值 $+1$ 需要花费 $c$ 。求需要使其中的 $k$ 个贡献值相等的最小花费。 $2≤n,k≤200000$，$1≤b,c≤2000$，|$v_i$|≤1e9 输入 第一行:$n,k,b,c$ 第二行:$v_1$ , $v_2$ ,…, $v_n$ 输出 使其中的 $k$ 个贡献值相等的最小花费。 ~~之前不知道为什么一堆乱码可能是我太弱了吧~~

Codeforces is a wonderful platform and one its feature shows how much someone contributes to the community. Every registered user has contribution — an integer number, not necessarily positive. There are $ n $ registered users and the $ i $ -th of them has contribution $ t_{i} $ . Limak is a little polar bear and he's new into competitive programming. He doesn't even have an account in Codeforces but he is able to upvote existing blogs and comments. We assume that every registered user has infinitely many blogs and comments. - Limak can spend $ b $ minutes to read one blog and upvote it. Author's contribution will be increased by $ 5 $ . - Limak can spend $ c $ minutes to read one comment and upvote it. Author's contribution will be increased by $ 1 $ . Note that it's possible that Limak reads blogs faster than comments. Limak likes ties. He thinks it would be awesome to see a tie between at least $ k $ registered users. To make it happen he is going to spend some time on reading and upvoting. After that, there should exist an integer value $ x $ that at least $ k $ registered users have contribution exactly $ x $ . How much time does Limak need to achieve his goal?

The first line contains four integers $ n $ , $ k $ , $ b $ and $ c $ ( $ 2<=k<=n<=200000,1<=b,c<=1000 $ ) — the number of registered users, the required minimum number of users with the same contribution, time needed to read and upvote a blog, and time needed to read and upvote a comment, respectively. The second line contains $ n $ integers $ t_{1},t_{2},...,t_{n} $ ( $ |t_{i}|<=10^{9} $ ) where $ t_{i} $ denotes contribution of the $ i $ -th registered user.

Print the minimum number of minutes Limak will spend to get a tie between at least $ k $ registered users.

4 3 100 30
12 2 6 1

220

4 3 30 100
12 2 6 1

190

6 2 987 789
-8 42 -4 -65 -8 -8

0

In the first sample, there are $ 4 $ registered users and Limak wants a tie between at least $ 3 $ of them. Limak should behave as follows. - He spends $ 100 $ minutes to read one blog of the $ 4 $ -th user and increase his contribution from $ 1 $ to $ 6 $ . - Then he spends $ 4·30=120 $ minutes to read four comments of the $ 2 $ -nd user and increase his contribution from $ 2 $ to $ 6 $ (four times it was increaded by $ 1 $ ). In the given scenario, Limak spends $ 100+4·30=220 $ minutes and after that each of users $ 2,3,4 $ has contribution $ 6 $ . In the second sample, Limak needs $ 30 $ minutes to read a blog and $ 100 $ minutes to read a comment. This time he can get $ 3 $ users with contribution equal to $ 12 $ by spending $ 100+3·30=190 $ minutes: - Spend $ 2·30=60 $ minutes to read two blogs of the $ 1 $ -st user to increase his contribution from $ 2 $ to $ 12 $ . - Spend $ 30+100 $ minutes to read one blog and one comment of the $ 3 $ -rd user. His contribution will change from $ 6 $ to $ 6+5+1=12 $ .