P12413 「YLLOI-R1-T2」圣诞星


小 Y 在商店里一共要买 $n$ 个商品，第 $i$ 个要买的商品价格为 $a_i$ 元。 在买这些商品前，小 Y 可以买任意多张优惠券，对于每一张优惠券，其价格为 $w$ 元。每有一张优惠券，在买任何商品时可以优惠 $1$ 元，但任何一个商品最低只能优惠到 $0$ 元。（优惠券不算商品） 在付钱过程中，每付完一个商品的钱，小 Y 还能再获得一张优惠券。 现在小 Y 想知道，最少需要多少钱才可以买完自己要买的商品。 注：所有的优惠券都是永久性的。

无

无

#### 【样例解释#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$。