Mô tả
Anh Nam là nhân viên chăm sóc khách hàng của Viettel. Cuối tháng, anh nhận được một danh sách gồm nhiều gói data 4G khuyến mãi, mỗi gói có dung lượng (tính bằng MB) khác nhau. Khách hàng thoả thuận chỉ nhận thêm tối đa K MB trong kỳ thanh toán này để tránh bị trừ cước vượt gói cước đang dùng.
Nhiệm vụ của bạn là giúp anh Nam chọn ra một tập con các gói data sao cho tổng dung lượng không vượt quá K, đồng thời tổng dung lượng nhận được phải lớn nhất có thể. Mỗi gói chỉ được chọn nhiều nhất một lần.
Đầu vào
- Dòng đầu chứa hai số nguyên
nvàK(1 ≤ n ≤ 10^5, 1 ≤ K ≤ 10^9). - Dòng thứ hai chứa
nsố nguyên dương, mỗi số là dung lượng một gói data (1 ≤ dung lượng ≤ 10^6).
Đầu ra
- In ra một số nguyên duy nhất: tổng dung lượng data lớn nhất có thể chọn mà không vượt quá
K.
Ràng buộc
- 1 ≤ n ≤ 10^5.
- 1 ≤ K ≤ 10^9.
- 1 ≤ dung lượng mỗi gói ≤ 10^6.
- Tổng dồn tích các phần tử được chọn luôn nằm trong phạm vi số nguyên 64-bit (không quá 10^9 trong mọi trường hợp thực tế).
Ví dụ
Ví dụ 1:
Đầu vào: 5 10 4 2 7 1 3
Đầu ra: 10
Giải thích: Ta có danh sách gói data [4, 2, 7, 1, 3] với ngưỡng K = 10. Sắp xếp giảm dần ta được [7, 4, 3, 2, 1]. Chọn 7 (tổng = 7), chọn tiếp 4 (tổng = 11 > 10, bỏ qua), chọn tiếp 3 (tổng = 10). Tổng lớn nhất đạt được là 10.
Ví dụ 2:
Đầu vào: 4 100 20 30 50 60
Đầu ra: 100
Giải thích: Sắp xếp giảm dần: [60, 50, 30, 20]. Chọn 60 (tổng = 60), chọn 50 (tổng = 110 > 100, bỏ qua), chọn 30 (tổng = 90), chọn 20 (tổng = 110 > 100, bỏ qua). Kết quả là 90.