题目描述

xht37 正在玩一款著名的卡牌游戏。

在这个游戏中，有 $n$ 种表情可以使用，使用第 $i$ 种表情一次可以为对方增加 $a_i$ 点快乐值。

你现在有 $m$ 次使用表情的机会，每种表情可以使用零次或任意多次。但任意一款表情不能连续使用超过 $k$ 次。

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

输入格式

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

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

输出格式

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

说明/提示

$2 \le n \le 2 \cdot 10^5,1 \le k \le m \le 2 \cdot 10^9,1 \le a_i \le 10^9$

样例

6 9 2
1 3 3 7 4 2

54

3 1000000000 1
1000000000 987654321 1000000000

1000000000000000000