Trong khu vườn, người ta trồng một hàng cây chạy dài gồm có ~N~ cây, mỗi cây có độ cao là ~a_1, a_2,...a_n~. Người ta cần lấy ~M~ mét gỗ bằng cách đặt cưa máy sao cho lưỡi cưa ở độ cao ~H~ (mét) để cưa tất cả các cây có độ cao lớn hơn ~H~ (dĩ nhiên những cây có độ cao không lớn hơn ~H~ thì không bị cưa).

Ví dụ: Nếu hàng cây có các cây với độ cao tương ứng là 20, 15, 10 và 18 mét, cưa lấy 7 mét gỗ. Lưỡi cưa đặt tại độ cao hợp lí là 15 mét thì độ cao của các cây còn lại sau khi bị cưa tương ứng là 15, 15, 10 và 15 mét. Tổng số mét gỗ lấy được là 8 mét (dư 1 mét).

Yêu cầu

Hãy tìm vị trí đặt lưỡi cưa hợp lí (số nguyên ~H~ lớn nhất) sao cho lấy được ~M~ mét gỗ và số mét gỗ dư ra là ít nhất.

Input

Dòng đầu chứa số nguyên ~N~ và ~M~ (~1 ≤ N ≤ 10^6~, ~1 ≤ M ≤ 2 \times 10^9~) cách nhau một dấu cách.

Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~ là độ cao của mỗi cây trong hàng (~1 ≤ a_i ≤ 10^9~, ~i = 1, ..., N~), mỗi số cách nhau ít nhất một dấu cách.

Output

Một số nguyên là giá trị cần tìm.

Sample Test

Input

4 7
20 15 10 18

Output

15