prithivMLmods/Coder-Stat

1 2 3 4<H1>スコーン配達計画</H1>5 6<p>7愛歌さんの家は、小さな喫茶店を経営しています。愛歌さんのお母さんが焼くスコーンはとても美味しくて、店はとても繁盛していました。8</p>9 10<p>11ウェイトレスである愛歌さんの仕事の一つは、次々と焼き上がるスコーンを、お客様の席まで届けることです。焼きあがったスコーンはお盆の上に乗せられ、カウンターの上に一列に並べられます。<var>i</var> 番目のお盆の上に乗っているスコーンの数を <var>K<sub>i</sub></var> としましょう。愛歌さんは、それぞれのお客様にちょうど <var>m</var> 個のスコーンを運ばなければなりません。愛歌さんは一度にいくつでもお盆を持つことができ、また複数のお盆から 1 人のお客様にスコーンを配ったり、１つのお盆から複数のお客様に配っても構いません。12</p>13 14<p>15喫茶店にはとてもたくさんのお客様がやってくるので、カウンターに置いてある全てのスコーンを運んでも、全てのお客様に届けることはできません。しかし、できるだけ多くのお客様に届けた後で、<var>m</var> 個に満たない数のスコーンが余ることもあるかもしれません。そのようなスコーンは、お手伝いのご褒美として、愛歌さんが貰えることになりました。16<!--スコーンはとても美味しいので、愛歌さんも大好きなのです。-->17</p>18 19<p>20ここでふと、愛歌さんは考えました。一度に全てのお盆を持つのではなく、一部のお盆だけを持ってお客様にスコーンを届けると、余るスコーンの数も違ってくるはずです。適切にお盆を選ぶことで、より多くのスコーンが余るようにできるかもしれません。愛歌さんは、作為的にお盆を選んでいることをお母さんに見抜かれないように、カウンターの上の1つの連続した範囲のお盆を選ぶことにしました。また、残ったお盆はお父さんやお母さんが運んでしまうので、愛歌さんがスコーンをもらうチャンスは一度しかありません。21</p>22 23<p>24さて、愛歌さんは最大いくつのスコーンを貰えるでしょうか？計算するプログラムを書いてください。お盆の数 <var>n</var> は 1 以上 30,000以下、 <var>m</var> は 1 以上 100,000 以下です。また数列の各要素 <var>K<sub>i</sub></var> は 0 以上 2<sup>32</sup>-1 です。25</p>26 27 28<h2>入力</h2>29 30<p>31複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。32</p>33 34<p>351行目 <var>n</var> <var>m</var>（整数 整数；半角空白区切り）<br>362行目 お盆上のスコーンの情報 <var>K<sub>1</sub></var> <var>K<sub>2</sub></var> ...  <var>K<sub>n</sub></var>（すべて整数 ; 半角空白区切り）<br>37<var>K<sub>i</sub></var>: <var>i</var>番目のお盆上のスコーンの数<br>38</p>39 40<p>41データセットの数は 50 を超えません。42</p>43 44 45<h2>出力</h2>46 47<p>48データセットごとに、もらえるスコーンの最大数を１行に出力します。49</p>50 51 52<h2>入力例</h2>53 54<pre>555 115611 27 34 45 56578 5580 2 1 5 4 6 8 3595 2602 4 2 4 66110 186210 15 12 31 12 50 11 23 43 181631 100645650 066</pre>67 68 69<h2>出力例</h2>70 71<pre>728734740751776577</pre>