Một nhà máy hoạt động trong \(2T+1\) ca theo thứ tự: đêm ngày \(0\), ban ngày ngày \(1\), đêm ngày \(1\), ban ngày ngày \(2\), đêm ngày \(2\), ..., ban ngày ngày \(T\), đêm ngày \(T\). Ứng viên \(i\) có kỹ năng \(A_i\), mức đóng góp \(B_i\), lương cơ bản \(C_i\) và ngày làm việc \(D_i\). Nếu được thuê, người đó làm đúng ba ca: đêm ngày \(D_i-1\), ban ngày ngày \(D_i\) và đêm ngày \(D_i\).

Trong mỗi ca, xếp tất cả người làm ca đó theo kỹ năng tăng dần rồi ghép người thứ \(1\) với thứ \(2\), thứ \(3\) với thứ \(4\), v.v. Mọi ca phải có số người chẵn; một ca không có ai làm vẫn hợp lệ. Với một cặp gồm người \(x\) có kỹ năng cao hơn người \(y\):

• Trong ca ban ngày, lợi nhuận sản xuất tăng \(B_x-B_y\); giá trị này có thể âm.
• Trong ca ban đêm, nhà máy trả tổng phụ cấp \(A_x-A_y\) cho cặp đó.

Tổng tiền lương bằng tổng lương cơ bản \(C_i\) của những người được thuê cộng toàn bộ phụ cấp ban đêm. Hãy chọn tập ứng viên hợp lệ để tối đa hóa tổng lợi nhuận sản xuất trừ tổng tiền lương, đồng thời in một tập đạt tối ưu.

Dữ liệu vào

• Dòng đầu: \(N\), \(T\).
• \(N\) dòng tiếp theo: \(A_i,B_i,C_i,D_i\).

Dữ liệu ra

In giá trị tối đa trên dòng thứ nhất và số công nhân được thuê \(K\) trên dòng thứ hai. Nếu \(K>0\), dòng thứ ba chứa \(K\) chỉ số đôi một khác nhau theo thứ tự bất kỳ; nếu \(K=0\), dòng này có thể rỗng hoặc được bỏ qua. Nếu có nhiều tập tối ưu, in bất kỳ tập nào.

Ràng buộc

• \(1\le T\le N\le500\).
• \(0\le A_i,B_i,C_i\le1000\), \(1\le D_i\le T\).
• Các \(A_i\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (13 điểm): \(N\le20\).
• Nhóm 2 (14 điểm): \(T=1\).
• Nhóm 3 (20 điểm): \(T\le10\).
• Nhóm 4 (22 điểm): với mọi \(1\le d\le T\), có không quá \(8\) ứng viên thỏa \(D_i=d\).
• Nhóm 5 (31 điểm): Không có ràng buộc bổ sung.

Ví dụ

6 2
21 0 1 1
13 25 0 2
22 20 3 2
20 5 2 2
4 23 0 2
25 16 8 1

7
4
1 3 4 6

Với tập này, lợi nhuận ban ngày là \(16+15=31\). Tổng phụ cấp ba ca đêm là \(4+4+2=10\), tổng lương cơ bản là \(14\), nên giá trị mục tiêu bằng \(31-(10+14)=7\). Cặp công nhân trong ca ngày và ca đêm có thể khác nhau vì mỗi ca đều ghép lại theo thứ tự kỹ năng.

5 2
40 23 10 1
59 22 2 2
32 7 10 2
52 30 0 1
38 10 3 1

0
0

12 3
6 19 4 2
32 0 1 3
12 0 4 3
25 7 0 2
35 15 5 1
28 25 5 2
19 27 3 3
30 13 3 2
1 24 5 3
20 11 0 2
2 1 5 2
24 28 3 2

20
8
1 3 4 6 7 10 11 12

Nguồn

KOI 2026 Round 2, problem Factory. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.