Bác thợ mộc cần thu hoạch ít nhất M mét chiều dài gỗ để đóng đồ nội thất. Trong rừng có N cây gỗ được trồng thành một hàng, cây thứ i có chiều cao là A_i mét. Bác thợ mộc sử dụng một chiếc máy cưa khổng lồ có thể cắt ngang tất cả các cây ở cùng một độ cao H.

Sau khi cắt, những phần ngọn cây nằm trên độ cao H sẽ bị đứt lìa và rớt xuống, đó chính là phần gỗ bác thu hoạch được. Những cây có chiều cao thấp hơn hoặc bằng H thì sẽ không bị cắt.

Yêu cầu

Bác thợ mộc muốn bảo vệ môi trường, nên bác muốn đặt độ cao H lớn nhất có thể để giữ lại phần gốc cây càng cao càng tốt, miễn là tổng lượng gỗ thu hoạch được lớn hơn hoặc bằng M. Hãy giúp bác tìm độ cao H đó.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên dương N và M cách nhau một khoảng trắng. Dòng thứ hai chứa N số nguyên dương A_1, A_2, ..., A_N cách nhau một khoảng trắng.

Dữ liệu ra

Ghi ra một số nguyên duy nhất là độ cao H lớn nhất cần tìm.

Ví dụ

Dữ liệu vào:
4 7
20 15 10 17

Dữ liệu ra:
15

Ràng buộc

Subtask 1 (50% số điểm): 1 <= N <= 1000; 1 <= M <= 10^6; 1 <= A_i <= 10^6.

Subtask 2 (50% số điểm): 1 <= N <= 10^6; 1 <= M <= 2*10^9; 1 <= A_i <= 10^9.