Chặt gỗ

Quân đang cần gấp \(M\) mét gỗ để đốt củi sưởi ấm mùa đông. May mắn là anh có một cái máy cưa có thể cắt mọi thứ, ở bất kì độ cao nào.

Máy cưa sẽ hoạt động như sau: Lúc đầu Quân sẽ chỉnh độ cao cắt của máy cưa, gọi độ cao đó là \(H\). Sau đó, máy cưa sẽ tự động bay lên, cắt một đường ngang, cây nào có độ cao lớn hơn \(H\) sẽ bị cắt trúng, và phần gỗ rơi xuống Quân sẽ lấy đi để đốt.

Ví dụ nếu các cây có độ cao lần lượt là \(20, 15, 15, 20, 25\), và \(H = 15\) thì cây thứ nhất và cây thứ tư mỗi cây bị cắt mất \(5\) m, cây thứ \(5\) bị cắt mất \(10\) m, tổng cộng là \(20\) m.

Yêu cầu: Hãy xác định độ cao \(H\) lớn nhất sao cho cắt ở độ cao \(H\) thì Quân sẽ thu được ít nhất \(M\) mét gỗ. Nếu cắt trụi \(N\) cây mà vẫn không đủ \(M\) mét gỗ, in ra \(-1\).

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) - số lượng cây.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_{1}, a_{2}, ..., a_{N}\) - độ cao lần lượt của các cây.

Output

Kết quả bài toán.

Example

4 7
20 15 10 17

15

5 20
4 42 40 26 46

36

Scoring

• \(50\%\) số test có \(N \leq 1000\), độ cao lớn nhất của các cây không vượt quá \(1000\) m.
• \(50\%\) số test còn lại có \(N \leq 10^6\), độ cao lớn nhất của các cây không vượt quá \(10^9\) m.

Đảm bảo trong tất cả các test, \(M \leq 10^9\).