伊万想吃一顿丰盛的晚餐。一顿好的晚餐应该包括第一道菜、第二道菜、一杯饮料和一份甜点。
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$$$。
在第二个例子中,唯一的第一道菜和第二道菜是坏的,所以不可能吃晚饭。