75 - ZOJ Monthly, February 2009 - H
As all you know, DD is a hospitable person. On Saint Valentine's Day, DD is going to arrang a party for girls and boys. However, as you may don't know, DD hate the so-called "8g" relationship. So, he will not invite a boy and a girl who have 8g at the same time.
DD's friends are M boys (labeled 1..M) and N girls (labeled 1..N), and each of them has a "lovely value". Now, DD want to invite some of them, satisfying that no 8g exists among invited people, and the total lovely value of all the invited people can be maximal.
Multiple test cases, each cases consists of three parts.
First part, one line, three integers M, N and S.
Second part, two lines. First line, M integers, boys' lovely values from the 1st to the Mth. Second line, N integers, girls' lovely values from the 1st to the Nth.
Third part, S lines. Each line consists of two integers X and Y, means that the boy X and the girl Y have 8g.
One blank line between test cases.
For each test case, your output should include three parts.
First part, one line, three integers X, A and B. X is the maximal total lovly value. A and B are the numbers of boys and girls invited.
Second part, one line, A integers, labels of the invited boys.
Third part, one line, B integers, labels of the invited girls.
If multiple solutions exist, output any of them.
0 <= M, N <= 100; 0 <= S <= M*N.
1 <= lovely value <= 1024.
5 5 10 1 3 5 7 9 2 4 6 8 10 1 4 5 3 2 4 3 5 1 1 2 4 1 2 3 4 1 5 5 5
37 1 5 4 1 2 3 4 5
Author: CUI, Tianyi
Source: ZOJ Monthly, February 2009