← 返回题目列表

Codeforces · 639/D

D. 熊与贡献

中文机器翻译题面 查看原题

Codeforces 是一个很棒的平台,它的一个功能显示了某人为社区做出了多少贡献。每个注册用户都有贡献——一个整数,不一定是正数。有n个注册用户,其中第i个有贡献ti。

Limak 是一只小北极熊,他是竞争性节目的新手。他甚至没有 Codeforces 帐户,但他可以对现有博客和评论进行投票。我们假设每个注册用户都有无限多的博客和评论。

- Limak 可以花 b 分钟阅读一篇博客并对其进行投票。作者贡献度将增加5。
- Limak 可以花 c 分钟阅读一条评论并对其进行投票。作者的贡献将增加1。

请注意,Limak 阅读博客的速度可能比评论快。

Limak 喜欢领带。他认为如果能看到至少 k 个注册用户之间存在平局那就太棒了。为了实现这一目标,他将花一些时间阅读和投票。之后,应该存在一个整数值x,至少k个注册用户的贡献恰好为x。

Limak 需要多少时间才能实现他的目标?

输入

第一行包含四个整数 n、k、b 和 c (2 ≤ k ≤ n ≤ 200 000, 1 ≤ b, c ≤ 1000)——分别是注册用户数、具有相同贡献的最小用户数、阅读和点赞博客所需的时间以及阅读和点赞评论所需的时间。

第二行包含 n 个整数 t1, t2, ..., tn (|ti| ≤ 109),其中 ti 表示第 i 个注册用户的贡献。

输出

打印 Limak 在至少 k 个注册用户之间取得平局所需花费的最少分钟数。

示例

输入 #1

4 3 100 30
12 2 6 1

输出 #1

220

输入 #2

4 3 30 100
12 2 6 1

输出 #2

190

输入 #3

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

输出 #3

0

注意

在第一个示例中,有 4 个注册用户,Limak 希望其中至少 3 个用户之间存在平局。 Limak 的行为应如下。

- 他花了 100 分钟阅读第 4 个用户的一篇博客,并将其贡献度从 1 增加到 6。
- 然后他花了 4·30 = 120 分钟阅读第二个用户的 4 条评论,并将其贡献从 2 增加到 6(增加 1 的四倍)。

在给定的场景中,Limak 花费了 100 + 4·30 = 220 分钟,之后用户 2、3、4 中的每个人都有贡献 6。

在第二个示例中,Limak 需要 30 分钟阅读博客,100 分钟阅读评论。这次他花费 100 + 3·30 = 190 分钟可以获得 3 个贡献度等于 12 的用户:

- 花费 2·30 = 60 分钟阅读第 1 个用户的两篇博客,将他的贡献从 2 增加到 12。
- 花费 30 + 100 分钟阅读第 3 个用户的一篇博客和一条评论。他的贡献将从 6 变为 6 + 5 + 1 = 12。