山手線は便利である。 なぜならば、130円払うだけで時間の許す限り何周でも乗っていられるからだ。ただし、切符で乗車する場合は、切符の有効時間に気をつけなければならない。ICカードなら安心らしい。この山手線の特性を利用して、東京近郊には電車に揺られながら惰眠を貪る輩が存在する。ちなみに、この問題の作問者はやったことがない。駅員にバレることは稀だろうが、バレたらめんどくさそうなので、オススメはしない。
山手線の特性を利用したゲームをしよう。 ここでは一般化のため、1からNで番号付けられたN個の駅があり、1, 2, ..., Nの順で駅が円上に並び、各駅からいずれの駅へ行くにもd円で乗車可能な路線として山手線モドキを考えることにする。ゲームは以下のルールに従う。
さて、あなたは最大で何円儲けることができるだろうか。ぜひ、挑戦してみて欲しい。
N d p_1 p_2 … p_N
入力はすべて整数からなる。 1行目には、山手線モドキの駅の数Nと乗車賃dが空白区切りで与えられる。 2行目には、各駅でもらえる報酬が空白区切りで与えられ、i番目の値p_iは駅iの報酬を表している。
ゲームで得られる金額の最大値を1行に出力せよ。1円以上の金額を得ることができない場合は"kusoge"と1行に出力せよ。出力の最後は改行し余計な文字を含んではならない。
5 130 130 170 100 120 140
50
3 100 100 90 65
kusoge
6 210 300 270 400 330 250 370
660
4 540 100 460 320 280
kusoge