#CSPX20241. 购物

购物

当前没有测试数据。

Background

双十一,很多人在疯狂地购物。

商家推出了各种各样的优惠活动,吸引顾客购买更多的商品。

某商家推出如下的优惠活动:

该商家共有 n 件商品,单独购买第 i 件商品的费用为 ai_i。顾客也可以花费 w 购买 一张优惠券,一张优惠券最多可兑换 m 件商品(无需额外付费)。顾客可以购买任意张优惠券;

如果最后商品不足 m 件,优惠券也可以使用。

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

Format

Input

第一行有 3 个整数 n,m,w。

第二行有 n 个整数,第 i 个为 ai_i,表示第 i 件商品的费用。

Output

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

Samples

5 2 8
2 7 1 8 4
15

Limitation

对于 30% 的数据,满足 1≤n≤103^3,1≤m≤103^3,1≤w≤109^9,1≤ai_i≤109^9

对于 100% 的数据,满足 1≤n≤2×105^5,1≤m≤2×105^5,1≤w≤109^9,1≤ai^i≤109^9