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à a1, a2,..., aN.

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ần 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 thứ nhất chứa 2 số nguyên dương N và M (1≤N≤10^6; 1≤M≤2.10^9) cách nhau một dấu cách.

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

Output

Kết quả: Ghi ra một số nguyên cho biết giá trị cần tìm.

Ví dụ

Input

4 7
20 15 10 18

Output

15