Description

In a Chinese textbook, HansBug found an answer key, but he clearly remembered that the book should also come with a workbook. However, there are too many items in front of him to count, including books, answer keys, and workbooks. A complete set should contain and only contain one book, one workbook, and one answer key, but everything is in a mess now. Although many labels have faded, HansBug can still roughly tell whether an item is a book, a workbook, or an answer key. He also roughly knows the possible correspondences between a book and an answer key, and between a book and a workbook (that is, he only knows which book and which answer key, and which book and which workbook could possibly correspond; all other pairs are impossible). Given this information, HansBug wants to know the maximum number of complete sets that can be formed simultaneously.

Input Format

The first line contains three positive integers $N_1,N_2,N_3$, representing the numbers of books, workbooks, and answer keys respectively.

The second line contains a positive integer $M_1$, representing the number of possible correspondences between books and workbooks.

Each of the next $M_1$ lines contains two positive integers $x,y$, indicating that book $x$ and workbook $y$ could correspond. ($1\leq x \leq N_1$, $1 \leq y \leq N_2$)

The next line contains a positive integer $M_2$, representing the number of possible correspondences between books and answer keys.

Each of the next $M_2$ lines contains two positive integers $x,y$, indicating that book $x$ and answer key $y$ could correspond. ($1 \leq x \leq N_1$, $1 \leq y \leq N_3$)

Output Format

Output a single positive integer, the maximum possible number of complete sets.

5 3 4
5
4 3
2 2
5 2
5 1
5 3
5
1 3
3 1
2 2
3 3
4 3

2

Hint

Sample explanation:

As described, $N_1=5$, $N_2=3$, $N_3=4$, meaning there are $5$ books, $3$ workbooks, and $4$ answer keys.

$M_1=5$, meaning there are $5$ possible correspondences between books and workbooks, namely: book $4$ with workbook $3$, book $2$ with workbook $2$, book $5$ with workbook $2$, book $5$ with workbook $1$, and book $5$ with workbook $3$.

$M_2=5$, meaning there are $5$ possible correspondences between books and answer keys, namely: book $1$ with answer key $3$, book $3$ with answer key $1$, book $2$ with answer key $2$, book $3$ with answer key $3$, and book $4$ with answer key $3$.

Therefore, at most two complete sets can be formed simultaneously in this case, namely: book $2$ + workbook $2$ + answer key $2$, and book $4$ + workbook $3$ + answer key $3$.

Constraints:

• For testdata points $1,2,3$, $1\le M_1,M_2\leq 20$.
• For testdata points $4\sim 10$, $1\le M_1,M_2 \leq 20000$.

Translated by ChatGPT 5