% Author: Sergey Kopeliovich
% Source: SPbSU Championship #35, 2013.04.14

\gdef\thisproblemauthor{Sergey Kopeliovich}
\gdef\thisproblemdeveloper{Sergey Kopeliovich}
\begin{problem}{Maximal Matching}
{matching.in}{matching.out}
{3.5 seconds (\textsl{5 seconds for Java})}{256 mebibytes}{}

You are given a bipartite graph.
Each vertex has some weight.
The weight of an edge is the sum of weights of its ends.
The weight of a matching is the sum of weights of edges of the matching.
You have to find a matching with maximal weight.
Note that the matching may contain any number of edges, the only constraint
is that its weight should be maximal possible.

Recall that a matching in a bipartite graph is a collection of edges
of the graph such that no two edges share a common vertex.

\InputFile

The first line contains the sizes of parts of the bipartite graph $n$ and $m$
($1 \le n, m \le 5\,000$) and the number of edges $e$ ($0 \le e \le 10\,000$).
The second line contains $n$ integer numbers from $0$ to $10\,000$ --- weights
of vertices of the first part.
The third line contains $m$ integer numbers from $0$ to $10\,000$ --- weights
of vertices of the second part.
Next $e$ lines contain the edges of the graph.
Each edge is described by a pair of integer numbers $a_i$ $b_i$,
where $1 \le a_i \le n$ is the number of vertex in the first part
and $1 \le b_i \le m$ is the number of vertex in the second part.

\OutputFile

On the first line output $w$ --- the maximal weight of matching.
On the second line output $k$ --- the number of edges in a matching
with maximal weight.
Next line should contain $k$ different numbers from $1$ to $e$ --- numbers
of edges from the matching.
If there are several matchings with maximal weight,
you may output any one of them.

\Examples

\begin{example}
\exmp{
4 3 3
2 0 9 9
1 0 9
1 2
2 1
1 1
}{
3
1
3
}%
\exmp{
3 2 4
1 2 3
1 2
1 1
2 1
2 2
3 2
}{
8
2
4 2
}%
\end{example}

\end{problem}
