Một siêu thị cần tuyển một số nhân viên bán hàng. Giờ làm việc trong mỗi ngày được tính từ thời điểm tới thời điểm Có ứng viên đánh số từ tới . Ứng viên thứ chỉ có thể làm từ thời điểm tới thời điểm trong ngày nếu được tuyển dụng và ứng viên đó yêu cầu mức lương mỗi ngày là .
Yêu cầu: Hãy giúp siêu thị tuyển một số nhân viên bán hàng trong số các ứng viên sao cho: Bất kỳ thời điểm nào trong giờ làm việc cũng có ít nhất một nhân viên bán hàng và tổng tiền lương phải trả trong mỗi ngày cho các nhân viên là ít nhất.
Dữ liệu:
Dòng đầu chứa số nguyên dương và số nguyên dương ;
dòng tiếp theo, dòng thứ chứa ba số nguyên .
Kết quả:
Dòng đầu ghi tổng tiền lương phải trả mỗi ngày cho các nhân viên theo phương án tìm được;
Dòng thứ hai ghi chỉ số những ứng viên được chọn trong phương án tìm được theo thứ tự tùy ý.
Các số trên một dòng ghi cách nhau ít nhất một dấu cách. Dữ liệu vào luôn đảm bảo tồn tại phương án tuyển dụng theo yêu cầu đặt ra. Nếu có nhiều phương án cùng tối ưu, chỉ đưa ra một phương án.
Ví dụ:
Dữ liệu:
5 8
0 2 10
0 4 30
1 7 90
3 7 60
7 8 10
Kết quả:
100
2 4 5
Ghi chú: Nếu thí sinh chỉ trả lời đúng dòng thứ nhất thì được số điểm của test.
