Khuyến mại

Sau đại dịch COVID-19 để kích cầu tiêu dùng các siêu thị đã đưa ra hàng loạt các chương trình khuyến mại. Một siêu thị đang có đợt khuyến mãi đặc biệt cho khách hàng. Siêu thị có n sản phẩm, các sản phẩm có giá tiền là a_i (VNĐ) (1 ≤ i ≤ n). Nếu khách hàng mua tất cả n sản phẩm của siêu thị, siêu thị sẽ cho khách hàng trả giá với cách sau: Khách hàng đưa ra một mức giá m, tất cả các sản phẩm nào có giá tiền lớn hơn m thì khách hàng được quyền mua đồng giá với giá tiền là m, ngược lại thì khách hàng có thể mua với giá đúng giá tiền của nó. Điều kiện ràng buộc: sau khi khách hàng đưa ra mức giá m, thì tổng số tiền mà khách hàng phải trả phải lớn hơn hoặc bằng một số S do siêu thị đưa ra. (0 ≤ S ≤ tổng số tiền của n sản phẩm).

Ví dụ: Trong siêu thị có ba món hàng trị giá 30, 50, 90 và siêu thị yêu cầu S = 140. Nếu khách hàng trả giá với m = 60, thì khách hàng sẽ mua 3 món hàng này với giá 30, 50, 60. Tổng số tiền mà khách hàng phải trả là 140 (VNĐ), đây là số tiền nhỏ nhất mà khách hàng phải trả và thỏa mãn điều kiện của siêu thị. Khách hàng không thể đưa ra giá m = 59, vì số tiền phải trả là 139 (VNĐ) chưa thỏa mãn điều kiện của siêu thị.

Yêu cầu: Em hãy lập trình giúp người khách hàng tìm ra số m tối ưu để số tiền phải trả là nhỏ nhất.

Dữ liệu: Vào từ tệp văn bản DISCOUNT.INP gồm hai dòng:

+ Dòng thứ nhất gồm hai số nguyên dương n và S (n ≤ 10⁵, S ≤ 10⁹).

+ Dòng thứ hai gồm n số nguyên dương a₁, a₂, …, a_n (1 ≤ a₁, a₂, …, a_n ≤ 10⁶) là giá của n sản phẩm.

Hai số ghi trên một dòng cách nhau bởi một dấu cách.

Kết quả: Ghi ra tệp văn bản DISCOUNT.OUT một số nguyên là kết quả bài toán.

Ví dụ:

Chấm điểm:

Subtask 1 (50%) : 1 ≤ n, a_i < 1000; i = 1, 2, ..., n;

Subtask 2 (50%) : Không có ràng buộc gì thêm.