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\le N\le 10^6; 1\le M\le 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\le a_i\le 10^9, 1\le i\le n)~, mỗi số cách nhau ít nhất một dấu cách.

Output

• Một dòng duy nhất ghi một số nguyên cho biết giá trị cần tìm.

Example

Input

4 7
20 15 10 18

Output

15