% Автор: Сергей Копелиович                
% Источник: 35-й чемпионат СПбГУ, 2013.04.14

\gdef\thisproblemauthor{Сергей Копелиович}
\gdef\thisproblemdeveloper{Сергей Копелиович}
\begin{problem}{Максимальное паросочетание}
{matching.in}{matching.out}
{3.5 секунды (\textsl{5 секунд для Java})}{256 мебибайт}{}

Дан двудольный граф.
У каждой вершины графа есть вес.
Вес ребра "--- сумма весов его концов.
Вес паросочетания "--- сумма весов рёбер, входящих в паросочетание.
Нужно найти паросочетание максимального веса.
Заметим, это паросочетание может содержать сколько угодно рёбер,
единственное условие "--- вес паросочетания должен быть максимальным.

Напомним, что паросочетанием в двудольном графе называется набор
рёбер этого графа такой, что никакие два ребра набора не имеют общих вершин.

\InputFile

В первой строке заданы размеры долей $n$ и $m$ ($1 \le n, m \le 5\,000$) и
количество рёбер $e$ ($0 \le e \le 10\,000$).
Вторая строка содержит $n$ целых чисел от $0$ до $10\,000$ "--- веса вершин
первой доли.
Третья строка содержит $m$ целых чисел от $0$ до $10\,000$ "--- веса вершин
второй доли.
Следующие $e$ строк содержат рёбра графа.
Каждое ребро описывается парой целых чисел $a_i$ $b_i$,
где $1 \le a_i \le n$ "--- номер вершины первой доли
и $1 \le b_i \le m$ "--- номер вершины второй доли.

\OutputFile

В первой строке выведите $w$ "--- максимальный вес паросочетания.
Во второй строке выведите $k$ "--- количество рёбер в паросочетании
максимального веса.
В следующей строке выведите $k$ различных чисел от $1$ до $e$ "--- номера
рёбер в паросочетании.
Если максимальных по весу паросочетаний несколько, разрешается вывести
одно любое.

\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}
