题目描述

双十一，很多人在疯狂地购物。商家推出了各种各样的优惠活动，吸引顾客购买更多的商品。某商家推出如下的优惠活动：

该商家共有 n 件商品，单独购买第 i 件商品的费用为 ai。顾客也可以花费 w 购买一张优惠券，一张优惠券最多可兑换 m 件商品（无需额外付费）。顾客可以购买任意张优惠券；如果最后商品不足 m 件，优惠券也可以使用。

求顾客购买完所有 n 件商品的最小费用。

输入格式

• 第一行有 3 个整数 n, m, w。
• 第二行有 n 个整数，第 i 个为 ai，表示第 i 件商品的费用。

输出格式

购买所有商品的最小费用。

样例输入 #1

5 2 8
2 7 1 8 4

样例输出 #1

5 2 8
2 7 1 8 4

样例输入 #2

5 3 8
6 7 4 8 9

样例输出 #2

16

样例 1 说明

花费 8 买一张优惠券，兑换第 2、第 4 件商品；第 1、第 3、第 5 件商品直接购买。共花费 8+2+1+4=15。

样例 2 说明

花费 16 购买两张优惠券，能兑换所有商品。

数据范围

• 30% 的数据：1≤n≤103，1≤m≤103，1≤w≤109，1≤ai≤109；
• 100% 的数据：1≤n≤2×105，1≤m≤2×105，1≤w≤109，1≤ai≤109。