Câu 3. Dãy số (4.0 điểm)

Cho dãy số nguyên dương \(a_1, a_2, \ldots, a_n\).
Mỗi thao tác bạn được phép chọn một phần tử bất kỳ trong dãy để tăng lên 1 đơn vị.

Yêu cầu:
Thực hiện \(m\) thao tác để phần tử nhỏ nhất của dãy (sau khi thực hiện \(m\) thao tác) nhận giá trị lớn nhất.

Input

Vào từ tệp CAU3.INP gồm:

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) \((1 \le n \le 2 \times 10^5,\; 0 \le m \le 10^{12})\);
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le 10^9)\).

Output

Ghi ra tệp CAU3.OUT một số nguyên duy nhất là giá trị nhỏ nhất của dãy số sau khi thực hiện \(m\) thao tác.

Example

5 6
2 8 6 5 9

6

Scoring

• Có 20% số điểm có \(n \le 10^5\) và \(m \le 1\);
• Có 20% số điểm có \(n = 2\) và \(m \le 10^2\);
• Có 30% số điểm có \(n \le 10^3\) và \(m \le 10^2\);
• 30% số điểm còn lại không có ràng buộc gì thêm.