#ABC153C. Fennec vs Monster

Fennec vs Monster

题目描述

Fennec is fighting with NN monsters.

The health of the ii-th monster is HiH_i.

Fennec can do the following two actions:

  • Attack: Fennec chooses one monster. That monster's health will decrease by 11.
  • Special Move: Fennec chooses one monster. That monster's health will become 00.

There is no way other than Attack and Special Move to decrease the monsters' health.

Fennec wins when all the monsters' healths become 00 or below.

Find the minimum number of times Fennec needs to do Attack (not counting Special Move) before winning when she can use Special Move at most KK times.

芬内克正在与 NN 只怪物战斗。

ii -th 怪物的_health_是 HiH_i

Fennec 可以采取以下两个行动:

  • 攻击芬内克选择一只怪物。该怪物的生命值将减少 11
  • 特殊移动:芬内克选择一只怪物。该怪物的生命值将变为 00

除了攻击和特殊移动之外,没有其他方法可以降低怪物的生命值。

当所有怪物的生命值都变为 00 或更低时,芬内克获胜。

当 Fennec 最多可以使用 KK 次特殊移动时,请找出她在获胜前最少需要的攻击次数(不包括特殊移动)。

输入格式

输入内容按以下格式标准输入:

NN KK
H1H_1 ...... HNH_N

输出格式

打印 Fennec 在获胜前最少需要进行的攻击次数(不包括特殊移动)。

样例 #1

样例输入 #1

3 1
4 1 5

样例输出 #1

5

样例 #2

样例输入 #2

8 9
7 9 3 2 3 8 4 6

样例输出 #2

0

样例 #3

样例输入 #3

3 0
1000000000 1000000000 1000000000

样例输出 #3

3000000000

说明

数据规模与约定

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 0K2×1050 \leq K \leq 2 \times 10^5
  • 1Hi1091 \leq H_i \leq 10^9
  • 所有输入值均为整数。

样例 11 解释

对第三只怪兽使用特殊移动,对第一只怪兽进行四次攻击,对第二只怪兽进行一次攻击,芬内克就能以五次攻击取胜。

样例 22 解释

她可以对所有怪物使用特殊移动。

样例 33 解释

小心溢出