Nhận xét :

Với một đơn hàng thì số tiền cần trả là giá của món quà đắt nhất của đơn hàng đó. Nên ta cần tìm cách để chọn những món quà càng đắt mà không cần phải trả tiền.

Từ đó ta có thuật toán tham lam : Với một dãy ~a_1 \le a_2... \le a_n~.

Ta sẽ xây dựng một đơn hàng có giá là ~a_n~ với nhiều món quà được chọn nhất có thể. Khi xây dựng xong, ta xóa dãy con của đơn hàng đó đi, và tiếp tục thực hiện cho đến khi không còn món quà nào.

Subtask 1

Ta sắp xếp lại giá của các món quà tăng dần. Thực hiện các thao tác như trên nhận xét.

Độ phức tạp : ~O(n ^ 2)~

Subtask 2

Ta có thể dùng ~\textbf{multiset}~ để thực hiện thao tác xây dựng đơn hàng và xóa các phần tử trong đơn hàng đó đi.

Độ phức tạp : ~O(n \times log(n))~