在 Byteland 大学，学生只能主修数学或计算机科学。目前有 $n$ 名数学系学生和 $m$ 名计算机科学系学生。由于这两个专业学习难度极大，没有人会同时修读这两个专业。

Byteasar 是该大学的校长。他希望组建一个学生团队来解决人类面临的所有难题。由于他知道每位学生的智商（IQ），他决定组建一个团队，使得团队成员的智商总和尽可能大。

然而，智商并不是全部。因此，校长希望团队中的所有成员都互相认识。已知所有数学系学生之间都互相认识，同样地，所有计算机科学系学生之间也都互相认识。

请编写一个程序，帮助校长组建一个团队，使得团队成员的智商总和最大，且团队中所有成员都互相认识。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m \le 400, 0 \le k \le n \cdot m$)，分别表示数学系学生人数、计算机科学系学生人数以及不同专业之间互相认识的学生对数。

接下来的 $k$ 行，每行描述一对认识关系：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le n, 1 \le b_i \le m$)，表示第 $i$ 对认识关系中数学系学生的编号和计算机科学系学生的编号。数学系学生和计算机科学系学生的编号均从 1 开始。

接下来的一行包含 $n$ 个整数，范围在 $[1, 10^9]$ 之间，表示各数学系学生的智商。再接下来的一行包含 $m$ 个整数，以相同格式表示各计算机科学系学生的智商。

输出格式

第一行应包含一个整数，等于满足 Byteasar 要求的团队中智商总和的最大值。

第二行应包含一个整数，表示 Byteasar 应选择的数学系学生人数。

第三行应包含这些学生的编号，以任意顺序排列。如果团队中没有数学系学生，则应打印一个空行。

接下来的两行应以类似格式描述团队中计算机科学系学生的编号。

如果存在多个最优解，输出其中任意一个即可。

样例

样例输入 1

3 2 3
1 1
2 1
2 2
1 3 1
1 2

样例输出 1

6
1
2
2
1 2