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, \ldots, 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 \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~ là độ cao của mỗi cây trong hàng (~1 ≤ a_i ≤ 10^9~, với ~i = 1 \ldots 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