#2795. 徐老师的战斗小队
-
ID: 2795
传统题
1000ms
256MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
徐老师的战斗小队
Description
徐老师最近为一款游戏设计了一个集合石系统这个系统能有效的解决玩家们找不到人组队下副本的问题
这个游戏中有四个职业：战士，法师，猎人，牧师
而一个完整的小队必然是四个职业各有一位
现在集合石中等待分配玩家中：
1. 战士有 $n_1$ 位，每位玩家的战斗力分别为 $a_1,a_2 \dots a_n$
2. 法师有 $n_2$ 位，每位玩家的战斗力分别为 $b_1,b_2 \dots b_n$
3. 猎人有 $n_3$ 位，每位玩家的战斗力分别为 $c_1,c_2 \dots c_n$
4. 牧师有 $n_4$ 位，每位玩家的战斗力分别为 $d_1,d_2 \dots d_n$
但是徐老师发现，有些玩家之间是处于仇敌关系的，这样关系的玩家如果分配在一起，会导致这个小队内部出现内讧，影响玩家的游戏体验
于是徐老师给集合石加了一个新系统，如果你有不想匹配到的玩家，可以设置他为黑名单，这样你们两人就不会被匹配在一起了
而这样的黑名单关系中：
1. $m_1$ 对是战士和法师之间的黑名单关系，$x,y$ 表示 $x$ 号战士玩家与 $y$ 号法师玩家不能匹配到一起
2. $m_2$ 对是法师和猎人之间的黑名单关系，$x,y$ 表示 $x$ 号法师玩家与 $y$ 号猎人玩家不能匹配到一起
3. $m_3$ 对是猎人和牧师之间的黑名单关系，$x,y$ 表示 $x$ 号猎人玩家与 $y$ 号牧师玩家不能匹配到一起
现在徐老师想知道，现有的所有玩家中，集合石能匹配出的小队中，战斗力之和最小的情况是多少
这样他才能设计副本难度，保证不论怎么匹配，玩家们都可以通过副本
Input Format
输入第一行包含四个整数 $n_1,n_2,n_3,n_4$ 分别表示四个职业的人数。第二行包含 $n_1$ 个整数，分别表示 $a_1, a_2 \dots a_n$
第三行包含 $n_2$ 个整数，分别表示 $b_1, b_2 \dots b_n$
第四行包含 $n_3$ 个整数，分别表示 $c_1, c_2 \dots c_n$
第五行包含 $n_4$ 个整数，分别表示 $d_1, d_2 \dots d_n$
下一行包含一个整数 $m_1$，表示战士和法师之间的黑名单关系有 $m_1$ 条
接下来的 $m_1$ 行每行包含两个整数 $x,y$ 表示 $x$ 号战士玩家与 $y$ 号法师玩家不能匹配到一起
用以上同样的方式输入法师和猎人的黑名单关系$m_2$以及猎人和牧师的黑名单关系$m_3$
对于 $10\%$ 的数据: $1 \leq n, m \leq 10$
对于 $50\%$ 的数据: $1 \le n, m \le 10^3$。
对于 $100\%$ 的数据: $1 \leq n, m\leq 150000，1\leq a_i,b_i,c_i,d_i\leq 10^8$。
特别的保证：$1\le x_i\le n_t$，$1\le y_i\le n_{t+1}$。
Output Format
如果无法组成小队则输出 `-1`，否则输出最小的战斗力之和4 3 2 1
1 2 3 4
5 6 7
8 9
10
2
1 2
1 1
2
3 1
3 2
1
1 126