Bạn đang chơi Minecraft, công việc của bạn là phải xây dựng một bức tường có độ cao lớn nhất có thể. Hiện tại, bạn đang có sẵn một bức tường có \(n\) cột, cột thứ \(i\) có chiều cao là \(a_{i}\). Hiện tại bạn có \(w\) khối, với mỗi khối bạn có thể nâng độ cao một cột bất kì thêm một đơn vị. Bạn muốn xây bức tường sao cho độ cao của cột có độ cao nhỏ nhất là lớn nhất có thể. Hỏi độ cao đó có thể bằng bao nhiêu?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(w\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq w \leq 10^{9})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \le 10^{9})\).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100, w \leq 10^{5}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{3}, w \leq 10^{6}\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

3 9 
1 1 1

4