背景

从某游戏中总结出来的题目

描述

小A在游戏里打怪。有一次,他一下子遇到了n个怪物。
每个怪物有一个生命值,第i个怪物的生命值是h_i。而小A除了生命值之外,还有一个属性是魔法值m。
小A和怪物们依次行动。每一回合,小A先行动,然后怪物们同时行动。
小A每次可以选择以下行动之一:
•普通攻击:令某个怪物的生命值减少1。
•重击:消耗1魔法值,令某个怪物的生命值减少2。
•群体攻击:消耗1魔法值,令全体怪物的生命值减少1。
而每个存活的怪物(生命值严格大于0)每次会令小A的生命值减少1。
假设小A有足够的生命值来维持存活,小A想知道自己至少需要被消耗多少生命值。

 

输入格式

第一行为两个数n和m。
第二行为n个整数,第i个数为h_i。

 

输出格式

输出一个整数,即小A至少被消耗的生命值。

样例输入与输出

输入1:
2 1
2 1
输出1:
1
说明:
以下三种策略都可以达到最优:
•第1回合重击怪物1,受到怪物2的攻击减少1点生命;第2回合普通攻击怪物2。
•第1回合群攻,受到怪物1的攻击减少1点生命;第2回合普通攻击怪物1。
•第1回合普通攻击怪物2,受到怪物1的攻击减少1点生命;第2回合重击怪物1。
输入2:
3 4
2 4 4
输出2:
6
说明:
前两个回合群攻,此时局面变为0 2 2,小A减少了5点生命;接下来两个回合分别重击两个怪物,小A又减少了1点生命。

数据范围与约定

  • 对于20%的数据,m≤0;
  • 对于30%的数据,m≤1;
  • 对于50%的数据,m≤18;
  • 存在30%的数据,n≤50,h_i≤50;
  • m=0与m=18各存在1个测试点,n≤1000,h_i≤1000;
  • 对于100%的数据,1≤n≤100,000,0≤m≤100,0<h_i≤100,000。

来源

原创