在運(yùn)動會上，小明從數(shù)軸的原點(diǎn)開始向正方向立定跳遠(yuǎn)。項(xiàng)目設(shè)置了 n 個檢查點(diǎn) a1, a2, . . . , an 且 ai ≥ ai?1 > 0。小明必須先后跳躍到每個檢查點(diǎn)上且只能跳躍到檢查點(diǎn)上。同時，小明可以自行再增加 m 個檢查點(diǎn)讓自己跳得更輕松。

在運(yùn)動會前，小明制定訓(xùn)練計(jì)劃讓自己單次跳躍的最遠(yuǎn)距離達(dá)到 L，并且學(xué)會一個爆發(fā)技能可以在運(yùn)動會時使用一次，使用時可以在該次跳躍時的最遠(yuǎn)距離變?yōu)?2L。小明想知道，L 的最小值是多少可以完成這個項(xiàng)目？

輸入共 2 行。

第一行為兩個正整數(shù) n, m。

第二行為 n 個由空格分開的正整數(shù) a1, a2, . . . , an。

輸出共 1 行，一個整數(shù)表示答案。

5 3
1 3 5 16 21

3

【樣例說明】

增加檢查點(diǎn) 10, 13, 19，因此每次跳躍距離為 2, 2, 5, 3, 3, 3, 2，在第三次跳躍時使用技能即可。

【評測用例規(guī)模與約定】

對于 20% 的評測用例，保證 n ≤ 102，m ≤ 103，ai ≤ 103。

對于 100% 的評測用例，保證 2 ≤ n ≤ 105，m ≤ 108，0 < ai ≤ 108。