Câu 4 đề thi thử HSG tỉnh, Yên Thành 2024-2025

Một công ty đang sở hữu ~n~ mỏ quặng, mỏ quặng thứ ~i~ (~1≤i≤n~) có trữ lượng là ~A_i~. Công ty vừa ký hợp đồng cung cấp lượng quặng là ~S~. Để có lượng quặng khai thác đủ cho hợp đồng, Ban giám đốc quyết định đưa ra phương án ở các mỏ như sau:

• Lựa chọn ra một giới hạn ~k~ và chỉ khai thác ở mỏ có trữ lượng lớn hơn ~k~.
• Các mỏ có trữ lượng lớn hơn ~k~ sẽ được khai thác cho đến khi trữ lượng đúng bằng ~k~.
• Lượng quặng khai thác thừa sẽ được lưu vào kho để phục vụ cho đơn hàng tiếp theo.

Yêu cầu:

Hãy giúp Ban giám đốc xác định giá trị ~k~ để khai thác đủ đảm bảo hợp đồng, và lượng quặng khai thác thừa là ít nhất.

Dữ liệu:

• Dòng 1: Chứa hai số nguyên dương ~n,S~ (~1≤n≤10^5~).
• Dòng 2: Ghi n số nguyên dương ~A_1, A_2, ..., A_n~ (~1 ≤A_i ≤ 10^9~ với ~i=1..n~). Dữ liệu đảm bảo ~S ≤ A_1+A_2+...+A_n~

  Kết quả:

Số nguyên ~k~ tìm được đảm bảo đủ lượng quặng cho hợp đồng và lượng quặng khai thác thừa là ít nhất.

Ví dụ

Input1

4 3
5 3 7 8

Output1

6

Input2

4 10
5 3 7 8

Output2

3

Giải thích test ví dụ

• Trong ví dụ 1, sẽ khai thác ở mỏ 3 và 4 với tổng là (7 – 6 ) + (8 – 6) = 3, vừa đủ quặng cần thiết.
• Trong ví dụ 2, sẽ khai thác ở mỏ 1, 3 và 4 với tổng là (5 – 3)+(7–3)+(8–3)= 11, lượng quặng thừa 1. Không có phương án tối ưu hơn.

Giới hạn:

• Có 30% số test ~n ≤ 1000~ và ~A_1 = A_2 = ... = A_n~ (~Ai ≤ 1000~)
• Có 40% số test khác ~n ≤ 1000~ và ~A_i ≤ 10^3~ (với mọi ~i~ thuộc [~1,n~])
• Có 30% số test còn lại không có ràng buộc gì thêm.