Bài 4

Công ty AMM đang sở hữu $N$ vườn sầu riêng, vườn thứ $i$ ($1 \le i \le N$) có trữ lượng quả là $a_i$. Công ty vừa ký hợp đồng cung cấp lượng sầu riêng là $S$. Để có lượng sầu riêng cung cấp đủ cho hợp đồng. Ban giám đốc quyết định đưa ra phương án thu hoạch ở các vườn sầu riêng như sau:

• Lựa chọn ra một giá trị $K$ và chỉ thu hoạch ở các vườn có trữ lượng lớn hơn $K$.
• Các vườn có trữ lượng lớn hơn $K$ sẽ được thu hoạch cho đến khi trữ lượng mỗi vườn đúng bằng $K$, ($K$ là một số nguyên không âm) thì dừng thu hoạch.

Yêu cầu: Hãy giúp Ban giám đốc xác định giá trị $K$ để thu hoạch tối thiểu số lượng sầu riêng đảm bảo hợp đồng sao cho số lượng sầu riêng thu hoạch thừa (nếu có) là ít nhất.

Đọc từ bàn phím theo cấu trúc sau:

• Dòng thứ nhất: Nhập hai số nguyên dương $N$ và $S$ ($1 \le N \le 10^5$);
• Dòng thứ hai: Nhập vào $N$ số nguyên dương $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^9$, $1 \le i \le N$).

Dữ liệu đảm bảo $S \le a_1 + a_2 + a_3 + \dots + a_N$, $S$ là một số nguyên dương.

Các số trên dòng cách nhau một khoảng trắng.

Xuất ra màn hình một số nguyên dương $K$ là giá trị để thu hoạch tối thiểu số lượng sầu riêng đảm bảo hợp đồng sao cho số lượng sầu riêng thu hoạch thừa (nếu có) là ít nhất.

• Có 30% số test tương ứng với 30% số điểm: $1 \le N \le 10^3$, $a_1 = a_2 = \dots = a_N$ và $a_i \le 10^3$;
• Có 40% số test tương ứng với 40% số điểm: $1 \le N \le 10^3$, $a_i \le 10^3$;
• Có 30% số test tương ứng với 30% số điểm không có ràng buộc gì thêm.