防御塔的完善

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 2 总提交人数: 3

题目描述

经过投入大量的人力物力之后,红萌馆的防御塔终于能够投入使用了。因为防御塔射程的限制,所以 防御塔只能起到保护红萌馆的作用,而不能利用它来进行攻击。野心勃勃的红萌馆主人remilia打算对防御塔进行改造,使得它能够完成远距离攻击手段,这 样就有把握再发动一次红魔异变。
由于Izayoi Sakuya最了解防御塔的结构,所以改造防御塔的重任就又落到了她身上。Izayoi Sakuya的初步打算是在防御塔的前面建一个魔法攻击炮台,防御塔的输出口会输出一种特殊的魔力,这种魔力都够被平炮台吸收,然后再由炮台进行分析处 理,最后决定攻击强度、攻击目标、魔法种类。这样魔法攻击炮台就会处在防御塔的保护当中了,在没有敌人威胁红萌馆安全时也可以利用防御塔和炮台的组合进行 攻击行动。
攻击炮台里面主要是一个魔力传输管道,它的长度一共为n + 2厘米,其中距离防御塔最近的1厘米用于接收防御塔的魔法能量,距离防御塔最远的一厘米用于输出攻击,剩下的n厘米用于分析魔力以及改变魔力性质。管道的 高度并不是统一的,距离防御塔i厘米到距离防御塔i+1厘米的高度为hi。当1单位魔力从高度高的管道传输到高度低的管道或者从高 度低的管道到高度高的管道会在这两个管道之间产生1单位的魔力残余,整个魔法攻击炮台进行攻击后产生的魔力残余为炮台内所有位置的魔力残余之和(从外界进 入炮台以及从炮台输出到外界时不会产生魔力残余)。如果管道内有魔力残余则不能进行攻击,因为有爆炸的风险。
已知消除1单位的魔力残余,需要等待1分钟时间,且h0 = h1, hn+1 = hn。现在Izayoi Sakuya想知道,她前一次攻击使用了k单位的魔力,至少需要等多少分钟才能再进行下一次攻击。

输入

输入有若干组数据,以EOF结束。
对于每组数据:
第一行有两个整数n,k。
接下来有n行,第i行有一个整数hi。
1 ≤ n ≤ 100,000, 1 ≤ k ≤ 10,000, 0 < hi < 1,000,000,000

输出

对于每组数据输出一行,第i行代表第i组数据的答案

输入样例

3 1
1
2
3
3 1
1
1
2

输出样例

2
1

Hint

对于第2组数据,前三厘米高度为1,后两厘米高度为2.在第三厘米处有1单位的魔力残余,所以就得等一分钟

相关推荐