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ầ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 ~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

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