32093번 - ジェットコースター 2 다국어

문제

JAG (Japan Amusement Group) は,観光客が多く訪れる国内有数の遊園地である.中でもジェットコースターは大人気アトラクションである.

今日も JAG は大盛況であり,ジェットコースター前には多数の団体客が列を作って待機している.アトラクションのスタッフであるあなたが確認したところ,待機列には現在 N グループの団体客が並んでおり,列の先頭から i 番目の団体は a_i 人からなるようである.

ジェットコースターには一度の運行で M 人まで搭乗可能であり,あなたはアトラクションの各運行ごとに以下のルールに従って客を座席へ案内する.これを待機列から客がいなくなるまで繰り返す.

1. 待機列が空になった場合,もしくは待機列先頭に並んでいる団体客の人数がジェットコースターの空席数より多い場合,ジェットコースターを発進させて現在の運行を終える.
2. 1 の条件に当てはまらない場合,待機列先頭の団体客全員をジェットコースターの空席へ案内する.
3. 1 に戻る.

閉園時間が近いことに気づいたあなたは,一組以下の隣接する団体客に待機順を入れ替わってもらうことで,アトラクション運行回数を削減できないかと考えた.具体的には以下の操作を 1 回以下行うことを考えている.

• 1 ≤ i ≤ N-1 を満たす整数 i を一つ選び,現在待機列先頭から i 番目に並んでいる団体客と i+1 番目に並んでいる団体客の待機順を入れ替える

最適に操作を行った場合,待機列を空にするまでに必要なアトラクション運行回数は最小で何回にできるだろうか?ただし,今後新規の客が待機列に追加されることも,待機中の客が列から離脱することもないものとする.

입력

入力は 50 個以下のデータセットからなる.各データセットは次の形式で表される.

N M

a₁ a₂ … a_N

一行目には整数 N, M が与えられる.N は待機中の団体客グループの数であり,2 ≤ N ≤ 2 × 10⁵ を満たす.M は一度の運行でジェットコースターに搭乗できる最大人数であり,1 ≤ M ≤ 10⁹ を満たす.

二行目には N 個の整数 a₁, a₂, ... , a_N が与えられる.a_i は待機列先頭から i 番目に並んでいる団体客の人数であり,1 ≤ a_i ≤ M を満たす.

また,すべてのデータセットに対する N の合計は 2 × 10⁶ を超えない.

入力の終わりは 2 つのゼロからなる行で表される.

출력

各データセットについて,最適な操作を行った場合に必要なアトラクション運行回数を1 行で出力せよ.

제한

힌트