円形のバームクーヘンがあります。円周上には \(N\) 個の切れ目候補があり、時計回りに \(1,2,\ldots,N\) の番号が付いています。
切れ目候補 \(i\) から切れ目候補 \(i+1\) までの時計回りの距離は \(A_i\) です。ただし、切れ目候補 \(N+1\) は切れ目候補 \(1\) を表すものとします。
あなたは \(N\) 個の切れ目候補のうち、ちょうど \(P\) 個を選んで切断します。選んだ切れ目によって、バームクーヘンは \(P\) 個のピースに分かれます。各ピースの長さは、円周上で隣り合う選択済み切れ目の間の時計回りの距離です。
\(P\) 個のピースのうち最も短いピースの長さを、できるだけ大きくしてください。その最大値を求めてください。
入力は以下の形式で標準入力から与えられます。
| \(N~P\) | |
| \(A_1~A_2~\ldots~A_N\) |
制約は以下の通りです。
最も短いピースの長さとして達成できる最大値を \(1\) 行に出力してください。
5 22 4 3 5 6
9
6 32 2 2 2 2 2
4
4 310 1 1 1
1
1 1100
100
8 41 3 2 6 4 2 5 3
6
サンプル1について:
切れ目候補 \(1\) と \(4\) を選ぶと、長さ \(2+4+3=9\) のピースと長さ \(5+6=11\) のピースに分かれます。このとき最も短いピースの長さは \(9\) で、これが最大です。