E. Дешевый обед
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иван хочет полноценно пообедать. Для этого он хочет заказать первое, второе, напиток и десерт.

Всего на выбор у Ивана есть $$$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$$$ несочетающихся пар из напитка и десерта.

Иван хочет купить ровно одно первое, одно второе, один напиток и один десерт так, чтобы они хорошо сочетались между собой и их общая стоимость была наименьшей возможной. Помогите ему найти самый бюджетный вариант!

Входные данные

В первой строке заданы четыре целых числа $$$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$$$. В противном случае выведите одно число — наименьшую суммарную стоимость обеда.

Примеры
Входные данные
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
Выходные данные
26
Входные данные
1 1 1 1
1
1
1
1
1
1 1
0
0
Выходные данные
-1
Примечание

Оптимальный вариант в первом примере — это выбрать первое блюдо номер $$$2$$$, второе номер $$$1$$$, напиток номер $$$2$$$ и десерт номер $$$1$$$.

Во втором примере, единственная пара из первого и второго не сочетается, а потому невозможно выбрать обед.