CF1117B.Emotes

There are $n$ emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The $i$-th emote increases the opponent's happiness by $a_i$ units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only $m$ times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than $k$ times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes $i$ and $j$ ($i \ne j$) such that $a_i = a_j$ are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.

在一款非常流行的数字收藏卡牌游戏（这款游戏十分著名，因此我们不提它的名字）中，共有 $n$ 个表情（emote）。第 $i$ 个表情会使对手的快乐值增加 $a_i$ 单位（众所周知，该游戏中的表情是用来让对手开心的）。

你仅有使用表情的总次数限制为 $m$ 次。你可以任意选择某个表情，使用一次、多次，或者完全不使用。唯一的限制是：不能连续使用同一个表情超过 $k$ 次（否则对手会认为你在故意戏弄他）。

注意：若两个表情 $i$ 和 $j$（$i \ne j$）满足 $a_i = a_j$，它们仍被视为不同的表情。

你的目标是使对手的快乐值尽可能高。请找出对手所能获得的最大快乐值。

The first line of the input contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le m \le 2 \cdot 10^9$) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is value of the happiness of the $i$-th emote.

输入的第一行包含三个整数 $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$ 个表情符号带来的快乐值。

Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.

输出一个整数——在满足题目要求的方式下使用表情符号时，对手的最大幸福感。

In the first example you may use emotes in the following sequence: $4, 4, 5, 4, 4, 5, 4, 4, 5$.

在第一个例子中，你可以按以下顺序使用表情符号：$4, 4, 5, 4, 4, 5, 4, 4, 5$。