← 返回题目列表

Codeforces · 1487/E

E. 便宜的晚餐

中文机器翻译题面 查看原题

伊万想吃一顿丰盛的晚餐。一顿好的晚餐应该包括第一道菜、第二道菜、一杯饮料和一份甜点。

Ivan 可以购买 $$$n_1$$$ 不同类型的第一道菜(第 $$$i$$$ 需要 $$$a_i$$$ 硬币),$$$n_2$$$ 不同类型的第二道菜(其中 $$$i$$$ 需要 $$$b_i$$$ 硬币),$$$n_3$$$ 不同类型的饮料(第$$$i$$$-第 $$$c_i$$$ 硬币)和 $$$n_4$$$ 不同类型的甜点(第 $$$i$$$-第 $$$d_i$$$ 硬币)。

有些菜品并不相配。有$$$m_1$$$对的第一道菜和第二道菜彼此不相配,$$$m_2$$$对的第二道菜和饮料,以及$$$m_3$$$对的饮料和甜点彼此不相配。

Ivan 想买一份第一道菜、一份第二道菜、一份饮料和一份甜点,这样它们彼此搭配得很好,并且晚餐的总费用尽可能最低。帮助他找到最便宜的晚餐选择!

输入

第一行包含四个整数 $$$n_1$$$、$$$n_2$$$、$$$n_3$$$ 和 $$$n_4$$$ ($$$1 \le n_i \le 150000$$$) — 分别是第一道菜、第二道菜、饮料和甜点的类型数量。

接下来是四行。第一行包含 $$$n_1$$$ 整数 $$$a_1, a_2, \dots, a_{n_1}$$$ ($$$1 \le a_i \le 10^8$$$),其中 $$$a_i$$$ 是第一门课程第 $$$i$$$ 类型的成本。接下来的三行以同样的方式表示第二道菜、饮料和甜点的费用($$$1 \le b_i, c_i, d_i \le 10^8$$$)。

下一行包含一个整数 $$$m_1$$$ ($$$0 \le m_1 \le 200000$$$) - 第一道菜和第二道菜不相配的对数。接下来的 $$$m_1$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le n_1$$$; $$$1 \le y_i \le n_2$$$) 表示第一个课程编号 $$$x_i$$$ 与第二个课程编号 $$$y_i$$$ 不匹配。所有这些对都是不同的。

彼此不相配的第二道菜和饮料的块以相同的格式给出。对于彼此不相配的成对饮料和甜点也是如此($$$0 \le m_2, m_3 \le 200000$$$)。

输出

如果无法选择第一道菜、第二道菜、饮料和甜点以使它们相互搭配,请打印 $$$-1$$$。否则,打印一个整数——晚餐的最低总费用。

示例

输入 #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 1

输出 #1

26

输入 #2

1 1 1 1
1
1
1
1
1
1 1
0
0

输出 #2

-1

注意

第一个示例中的最佳选择是第一道菜 $$$2$$$、第二道菜 $$$1$$$、饮料 $$$2$$$ 和甜点 $$$1$$$。

在第二个例子中,唯一的第一道菜和第二道菜是坏的,所以不可能吃晚饭。