J Baumkuchen Party

制限時間: 3 sec メモリ制限: 1024 MB

Baumkuchen Party

Statement

円形のバームクーヘンがあります。円周上には \(N\) 個の切れ目候補があり、時計回りに \(1,2,\ldots,N\) の番号が付いています。

切れ目候補 \(i\) から切れ目候補 \(i+1\) までの時計回りの距離は \(A_i\) です。ただし、切れ目候補 \(N+1\) は切れ目候補 \(1\) を表すものとします。

あなたは \(N\) 個の切れ目候補のうち、ちょうど \(P\) 個を選んで切断します。選んだ切れ目によって、バームクーヘンは \(P\) 個のピースに分かれます。各ピースの長さは、円周上で隣り合う選択済み切れ目の間の時計回りの距離です。

\(P\) 個のピースのうち最も短いピースの長さを、できるだけ大きくしてください。その最大値を求めてください。

Input

入力は以下の形式で標準入力から与えられます。

	\(N~P\)
	\(A_1~A_2~\ldots~A_N\)

制約は以下の通りです。

Output

最も短いピースの長さとして達成できる最大値を \(1\) 行に出力してください。

Examples

Input 1

5 2
2 4 3 5 6

Output 1

Input 2

6 3
2 2 2 2 2 2

Output 2

Input 3

4 3
10 1 1 1

Output 3

Input 4

1 1
100

Output 4

Input 5

8 4
1 3 2 6 4 2 5 3

Output 5

Note

サンプル1について:

切れ目候補 \(1\) と \(4\) を選ぶと、長さ \(2+4+3=9\) のピースと長さ \(5+6=11\) のピースに分かれます。このとき最も短いピースの長さは \(9\) で、これが最大です。