题目背景

题目描述

小 Y 在商店里一共要买 $n$ 个商品，第 $i$ 个要买的商品价格为 $a_i$ 元。

在买这些商品前，小 Y 可以买任意多张优惠券，对于每一张优惠券，其价格为 $w$ 元。每有一张优惠券，在买任何商品时可以优惠 $1$ 元，但任何一个商品最低只能优惠到 $0$ 元。（优惠券不算商品）

在付钱过程中，每付完一个商品的钱，小 Y 还能再获得一张优惠券。

现在小 Y 想知道，最少需要多少钱才可以买完自己要买的商品。

注：所有的优惠券都是永久性的。

输入格式

第一行两个整数 $n,w$。

第二行 $n$ 个整数 $a_i$。

输出格式

一个整数，表示小 Y 买完所有自己要买的商品所需的最少钱数。

4 3
3 4 5 5

9

4 3
4 4 3 3

7

提示

【样例解释#1】

下面展示一种最优方案。

先购买 $3$ 张优惠券，花费 $3\times 3=9$ 元。

接下来使用 $0$ 元购买第 $1$ 个要买的商品（$3$ 张优惠券优惠了 $3$ 元），并再获得一张优惠券。

接下来使用 $0$ 元购买第 $2$ 个要买的商品（$4$ 张优惠券优惠了 $4$ 元），并再获得一张优惠券。

接下来使用 $0$ 元购买第 $3$ 个要买的商品（$5$ 张优惠券优惠了 $5$ 元），并再获得一张优惠券。

接下来使用 $0$ 元购买第 $4$ 个要买的商品（$6$ 张优惠券优惠了 $5$ 元，因为任何一个商品最低只能优惠到 $0$ 元），并再获得一张优惠券。

因此一共花费 $9+0+0+0+0=9$ 元。

【样例解释#2】

下面展示一种最优方案。

先购买 $1$ 张优惠券，花费 $1\times 3=3$ 元。

接下来使用 $2$ 元购买第 $4$ 个要买的商品（$1$ 张优惠券优惠了 $1$ 元），并再获得一张优惠券。

接下来使用 $1$ 元购买第 $3$ 个要买的商品（$2$ 张优惠券优惠了 $2$ 元），并再获得一张优惠券。

接下来使用 $1$ 元购买第 $2$ 个要买的商品（$3$ 张优惠券优惠了 $3$ 元），并再获得一张优惠券。

接下来使用 $0$ 元购买第 $1$ 个要买的商品（$4$ 张优惠券优惠了 $4$ 元），并再获得一张优惠券。

因此一共花费 $3+2+1+1+0=7$ 元。

【数据范围】

本题采用捆绑测试。

• Subtask 1（10 pts）：$\forall a_i=i$。
• Subtask 2（10 pts）：$w=1$。
• Subtask 3（20 pts）：$n,a_i,w\le 10$。
• Subtask 4（30 pts）：$n,a_i,w\le 1000$。
• Subtask 5（30 pts）：无特殊限制。

对于全部数据，保证：$1\le n\le 10^5$，$1\le a_i,w\le 10^9$。