Welcome to ZOJ
75 - ZOJ Monthly, February 2009 - H
Party of 8g

Time Limit: 5 Seconds      Memory Limit: 56797 KB      Special Judge

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.

Data Restriction

0 <= M, N <= 100; 0 <= S <= M*N.

1 <= lovely value <= 1024.

Sample Input

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

Sample Output

37 1 5
1 2 3 4 5

Author: CUI, Tianyi
Source: ZOJ Monthly, February 2009
Submit    Status