問題説明

デザート店の店主が、陳列棚に高さがバラバラのケーキを立てて並べました。 店主はお客様向けの無料試食コーナーを作るため、カッターの刃をある高さHに合わせ、ケーキを「一度に」横に切ります。 するとHより高いケーキは上の部分が切り落とされ、その切れた上の部分をすべて集めて試食用ピースにします。（Hより低いケーキは刃に触れずそのまま残ります。） 刃の高さHが低いほど多く切れて試食量は増えますが、陳列用のケーキが台無しになります。そこで試食に必要な量はちょうど満たしつつ、陳列棚の損傷を最小にするため刃をできるだけ高く置きたいのです。 必要な試食量以上を集められる刃の高さHの最大値を求めてください。

入力

出力

制約条件

• •1 ≤ N ≤ 1,000,000
• •1 ≤ 各ケーキの高さ ≤ 1,000,000,000
• •1 ≤ M ≤ 2,000,000,000（全ケーキを高さ0で切れば常にM以上得られる）

例

6 18
15 22 9 18 30 25

19