题目描述

傲傲觉得自己太瘦了，于是决定在 $ty$ 信息学夏令营中通过体育锻炼来给自己增重！

一次偶然，他被神秘的 $JY$ 老师带到了一旁，递给了他一大箱魔法药水！这些魔法药水总共有 $n$ 种，每种魔法药水都有很多瓶，根本用不完！其中喝下一瓶第 $i$ 种魔法药水可以给傲傲增加 $w_i$ 的重量，傲傲欣喜若狂，准备把魔法药水全部给喝下去！

$JY$ 老师赶紧拦住傲傲，并告知了药水的规则：傲傲总共可以喝下 $m$ 瓶魔法药水，并且使用时，同一种魔法药水最多连续喝下 $k$ 瓶。如果超过了这些限制，就会适得其反！

因此小傲想知道，按照这样的规则喝下魔法药水，最多可以增长多大的重量呢？

输入格式

第一行，输入三个整数 $n$、$m$、$k$ 表示傲傲得到了 $n$ 种魔法药水，最多喝下 $m$ 瓶，每种药水最多连续喝下 $k$ 瓶。

输出格式

一个整数，输出最多可以增长的重量。

6 3 2 
1 3 3 7 4 2

18

3 1000000000 1 
1000000000 987654321 1000000000

1000000000000000000

数据范围

对于 $50\%$ 的数据，有 $2≤n≤5∗10^3,1≤k≤m≤5∗10^3$;

对于 $100\%$ 的数据，有 $2≤n≤5∗10^5,1≤k≤m≤5∗10^9,1≤w_i≤10^9$。