Yamanote-line Game

Time Limit : 2 sec, Memory Limit : 262144 KB

B: 山手線ゲーム - Yamanote-line Game -

豆(?)知識

山手線は便利である。 なぜならば、130円払うだけで時間の許す限り何周でも乗っていられるからだ。ただし、切符で乗車する場合は、切符の有効時間に気をつけなければならない。ICカードなら安心らしい。この山手線の特性を利用して、東京近郊には電車に揺られながら惰眠を貪る輩が存在する。ちなみに、この問題の作問者はやったことがない。駅員にバレることは稀だろうが、バレたらめんどくさそうなので、オススメはしない。

問題文

山手線の特性を利用したゲームをしよう。 ここでは一般化のため、1からNで番号付けられたN個の駅があり、1, 2, ..., Nの順で駅が円上に並び、各駅からいずれの駅へ行くにもd円で乗車可能な路線として山手線モドキを考えることにする。ゲームは以下のルールに従う。

  • 好きな駅をスタート地点に選びd円で山手線モドキに乗車する。
  • その後、任意の駅で降車し再度乗車することを繰り返す。
  • スタートした駅で降車した時点でゲーム終了となる。
  • i番目の駅で降りるとp_i円の報酬を得ることができる.
  • ただし、1度報酬を得た駅で再度報酬を得ることはできない。
  • また、降車した後に再度山手線モドキに乗車するにはd円かかる。

さて、あなたは最大で何円儲けることができるだろうか。ぜひ、挑戦してみて欲しい。

入力形式

N d
p_1 p_2p_N

入力はすべて整数からなる。 1行目には、山手線モドキの駅の数Nと乗車賃dが空白区切りで与えられる。 2行目には、各駅でもらえる報酬が空白区切りで与えられ、i番目の値p_iは駅iの報酬を表している。

制約

  • 3 ≤ N ≤ 1{,}000
  • 1 ≤ d ≤ 1{,}000
  • 1 ≤ p_i ≤ 1{,}000 (1 ≤ i ≤ N)

出力形式

ゲームで得られる金額の最大値を1行に出力せよ。1円以上の金額を得ることができない場合は"kusoge"と1行に出力せよ。出力の最後は改行し余計な文字を含んではならない。

入力例1

5 130
130 170 100 120 140

出力例1

50

入力例2

3 100
100 90 65

出力例2

kusoge

入力例3

6 210
300 270 400 330 250 370

出力例3

660

入力例4

4 540
100 460 320 280

出力例4

kusoge

Note

Link
 
Source: Aizu Competitive Programming Camp 2016 Day3 , Japan, 2016-09-19