题目描述

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

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

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

该商家共有 $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

15

5 3 8
6 7 4 8 9

16

说明与数据范围

样例解释

样例 $1$ 说明：

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

共花费 $8 + 2 + 1 + 4 = 15$。

样例 $2$ 说明：

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

数据范围

对于 $30\%$ 的数据，满足 $1 \leq n \leq 10^3,1 \leq m \leq 10^3,1 \leq w \leq 10^9,1 \leq a_i \leq 10^9$。

对于 $100\%$ 的数据，满足 $1 \leq n \leq 2 \times 10^5,1 \leq m \leq 2 \times 10^5,1 \leq w \leq 10^9,1 \leq a_i \leq 10^9$。

来源与本地评测说明

来源：洛谷 B4104。题面按来源整理，源题号保留。

本地测试数据自行构造，经过独立 Python 基准、边界对拍及 Linux C++17 沙箱核验，并非洛谷原版完整评测数据。本地训练分值归一为100分。原题提及但未提供的选手目录附件样例不在本地附件中；本页列出的输入输出样例完整保留。