Cho \(n\) cột, cột thứ \(i\) có độ cao là \(a_i\). Bạn cần thiết lập một mức chiều cao \(h\) (\(h \geq 1\)) sao cho tổng lượng nước đổ vào không vượt quá \(x\) đơn vị. Biết rằng, lượng nước cần để lấp đầy trên cột thứ \(i\) tới mức \(h\) là: \(\max(0, h - a_i)\).

Yêu cầu: Tìm giá trị nguyên lớn nhất của \(h\) sao cho tổng lượng nước sử dụng \(\leq x\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(x\) (\(1 \leq n \leq 2 \cdot 10^5; 1 \leq x \leq 10^{14}\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\)).

Output

• Ghi một số nguyên dương \(h\) duy nhất là chiều cao tối đa tìm được.

Example

7 9
3 1 2 4 6 2 5

4

4 1
1 4 3 4

2

3 10
1 1 1

4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000; x \leq 10^6; a_i \leq 1000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.