Trong buổi họp lớp, Alice đã chụp được bức ảnh, các bức ảnh được đánh số từ 1 đến . Bức ảnh thứ () có kích thước . Có bạn trong lớp muốn nhờ Alice sao chép các bức ảnh, bạn thứ () sẽ đưa cho Alice hai ổ đĩa: ổ đĩa thứ nhất có sức chứa , ổ thứ hai có sức chứa và một danh sách là các bức ảnh không cần sao chép.
Bạn thứ mong muốn có thể sao chép được nhiều bức ảnh nhất vào hai ổ đĩa gồm các bức ảnh không thuộc danh sách . Alice không chắc chắn có thể sao chép được tối đa các bức ảnh theo cách tối ưu. Tuy nhiên, bạn thứ vẫn vui vẻ nếu số lượng bức ảnh sao chép được không ít hơn , trong đó là số lượng tối đa các bức ảnh có thể sao chép được theo cách tối ưu.
Yêu cầu: Hãy giúp Alice đưa ra kế hoạch sao chép các bức ảnh cho các bạn. Giả sử là số lượng bức ảnh mà Alice có thể sao chép cho bạn thứ (), giá trị này được chấp nhận nếu .
Dữ liệu:
Dòng đầu chứa hai số nguyên dương ();
Dòng thứ hai chứa số nguyên dương ();
Dòng thứ () trong dòng sau, mỗi dòng có dạng:
Hai số đầu tiên là ();
Số thứ ba là là số bức ảnh mà bạn không thích;
Tiếp theo là số là chỉ số các bức ảnh thuộc danh sách .
Tổng số lượng phần tử trong danh sách không vượt quá ().
Kết quả:
Dòng đầu chứa số nguyên là số bức ảnh có thể sao chép cho bạn thứ nhất;
Dòng thứ hai là một xâu độ dài chỉ gồm các kí tự '0', '1', '2' mô tả cách sao chép các bức ảnh cho bạn thứ nhất, trong đó kí tự thứ () bằng '0' cho biết bức ảnh thứ không được sao chép, bằng '1' hoặc '2' cho biết bức ảnh được sao chép vào đĩa 1 hoặc đĩa 2;
Do dữ liệu ghi ra quá lớn nên với các bạn còn lại chỉ cần đưa ra số lượng bức ảnh có thể sao chép được. Cụ thể, dòng thứ ba chứa số .
Ví dụ:
Dữ liệu:
6 3
2 1 1 3 4 1
5 5 0
5 5 2 2 6
5 7 0
Kết quả:
5
111022
4 5
Giải thích:
Với bạn thứ nhất, tối đa các bức ảnh có thể sao chép được là 5 (ví dụ, đĩa 1 chứa bức ảnh 1, 2, 3; đĩa 2 chứa bức ảnh 5, 6). Kết quả đưa ra bằng 4 hoặc 5 đều được chấp nhận.
Với bạn thứ 2, tối đa các bức ảnh có thể sao chép được là 4 (ví dụ, đĩa 1 chứa bức ảnh 1, 4; đĩa 2 chứa bức ảnh 3, 5). Kết quả đưa ra bằng 3 hoặc 4 đều được chấp nhận.
Với bạn thứ 3, tối đa các bức ảnh có thể sao chép được là 6. Kết quả bằng 5 hoặc 6 đều được chấp nhận.
