← 返回题目列表

Codeforces · 1117/B

B. 表情

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

非常流行的数字收藏卡牌游戏中有 $$$n$$$ 表情(该游戏非常有名,所以我们不会说出它的名字)。第 $$$i$$$ 表情可以使对手的幸福度增加 $$$a_i$$$ 个单位(我们都知道这个游戏中的表情是用来让对手开心的)。

您只有时间使用某些表情 $$$m$$$ 次。你可以使用任何情绪一次、多次,或者根本不使用它。唯一的限制是你不能连续使用同一个表情超过 $$$k$$$ 次(否则对手会认为你在戏弄他)。

请注意,两个表情 $$$i$$$ 和 $$$j$$$ ($$$i \ne j$$$) 使得 $$$a_i = a_j$$$ 被视为不同。

你必须尽可能让你的对手高兴。找到最大可能的对手幸福感。

输入

输入的第一行包含三个整数 $$$n、m$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le m \le 2 \cdot 10^9$$$) — 表情符号的数量、可以使用表情符号的次数以及可以使用相同表情符号的最大次数连续表达情绪。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个表情的幸福值。

输出

打印一个整数 - 如果您以满足问题陈述的方式使用表情,则对手的最大幸福感。

示例

输入 #1

6 9 2
1 3 3 7 4 2

输出 #1

54

输入 #2

3 1000000000 1
1000000000 987654321 1000000000

输出 #2

1000000000000000000

注意

在第一个示例中,您可以按以下顺序使用表情:$$$4, 4, 5, 4, 4, 5, 4, 4, 5$$$。