#d. 购物（buy）

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

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

第二行有 $n$ 个整数，第 $i$ 个为 $a_i$ ，表示第 $i$ 件商品的费用。

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

5 2 8
2 7 1 8 4

样例 $1$ 说明：

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

5 3 8
6 7 4 8 9

样例 $2$ 说明：

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

$30 \%$ 的数据：$1\le n\le10^3,1\le m\le10^3,1\le w\le10^9,1\le a_i\le 10^9$；

$100 \%$ 的数据：$1\le n\le 2\times10^5,1\le m\le2\times10^5,1\le w\le10^9,1\le a_i\le 10^9$。