Bài 16: Nâng cấp đội hình

Yêu cầu: Là một huấn luyện viên trưởng, bạn đang nắm trong tay một đội hình gồm ~N~ cầu thủ. Cầu thủ thứ ~i~ có chỉ số sức mạnh là ~A_i~. Ban lãnh đạo cấp cho bạn một ngân sách để thực hiện tối đa ~K~ khóa huấn luyện đặc biệt. Mỗi khóa huấn luyện giúp tăng chỉ số sức mạnh của MỘT cầu thủ bất kỳ lên đúng ~1~ đơn vị. Bạn muốn đội bóng của mình phát triển đồng đều nhất có thể. Hãy tìm cách phân bổ các khóa huấn luyện sao cho chỉ số sức mạnh của cầu thủ yếu nhất trong đội là LỚN NHẤT có thể.

Giới hạn:

• ~1 \le N \le 10^5~
• ~1 \le A_i \le 10^9~
• ~1 \le K \le 10^{14}~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Ví dụ:

Input:

5 6
2 1 4 3 6

Output:

4

(Giải thích: Đội hình ban đầu: [2, 1, 4, 3, 6]. Ta có 6 khóa huấn luyện.)

• Dùng 2 khóa cho cầu thủ thứ 2 (1 -> 3). Mảng thành: [2, 3, 4, 3, 6]. Còn 4 khóa.
• Dùng 2 khóa cho cầu thủ thứ 1 (2 -> 4). Mảng thành: [4, 3, 4, 3, 6]. Còn 2 khóa.
• Dùng 1 khóa cho cầu thủ thứ 2 (3 -> 4) và 1 khóa cho cầu thủ thứ 4 (3 -> 4). Mảng cuối cùng: [4, 4, 4, 4, 6]. Cầu thủ yếu nhất có sức mạnh là 4.