题目描述

码小虎，正在玩一款著名的卡牌游戏。

在这个游戏中，有$n$种表情可以使用，使用第$i$种表情一次可以为对方增加$a_i$；点快乐值。 他现在有$m$次使用表情的机会，每种表情可以使用$0$次或任意多次。但任意一款表情不能连续使用超过 $k$次。

码小虎，想要算出他能给对方带来的快乐值最多是多少。他当然知道该怎么算，但是他想考考你。

输入

输入第一行包含三个整数$n,m,k。$

第二行包含$n$个整数，第$i$个整数 $a_i$，代表使用第$i$种表情一次能带来的快乐值。

输出

输出一个整数，即码小虎能给对方带来的最大快乐值。

样例

6 9 2
1 3 3 7 4 2

54

3 1000000000 1
1000000000 987654321 1000000000

1000000000000000000

提示

【数据范围】 $2≤n≤2×$$10^5$。 $1≤k≤m≤2×$$10^9$。 $1≤$$a_i$$≤$$10^9$。 对于 $30\%$ 的数据，具有相同快乐值的表情卡牌均不上一张。

来源

码极客原创