NGUỒN: Bài tập thầy Vũ Mạnh Hà - Ôn Hải Phòng 08/11/2020
Bờm di cư ra phố. Cậu cần vận chuyển món đồ bằng chiếc xe tải mượn được, tải trọng các xe lần lượt là , trọng lượng các món đồ lần lượt là . Cách thức Bờm xếp đồ lên xe là như sau: các món đồ sẽ lần lượt được xếp theo thứ tự , khi xe đang được xếp đầy hoặc không còn đủ tải thì mới chuyển sang xe khác, thứ tự các xe vào nhận đồ là tùy ý Bờm.
Bờm muốn tìm một thứ tự các xe vào nhận đồ sao cho với cách thức xếp các món đồ kể trên tổng tải trọng các xe không sử dụng là lớn nhất có thể. Hãy xác định giúp Bờm tổng tải trọng lớn nhất đó.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên ;
dòng tiếp theo chứa các số nguyên $𝑐_1, 𝑐_2, … , 𝑐_𝑀\ (1 ≤ 𝑐_𝑖 ≤ 10^9);
dòng tiếp theo chứa số nguyên .
Dữ liệu ra:
Một dòng duy nhất chứa số nguyên kết quả (số này bằng nếu Bờm không thể vận chuyển hết các món đồ).
