Иван хочет полноценно пообедать. Для этого он хочет заказать первое, второе, напиток и десерт.
Всего на выбор у Ивана есть \(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\) несочетающихся пар из напитка и десерта.
Иван хочет купить ровно одно первое, одно второе, один напиток и один десерт так, чтобы они хорошо сочетались между собой и их общая стоимость была наименьшей возможной. Помогите ему найти самый бюджетный вариант!
Выходные данные
Если невозможно выбрать первое, второе, напиток и десерт, сочетающиеся друг с другом, выведите \(-1\). В противном случае выведите одно число — наименьшую суммарную стоимость обеда.
Примечание
Оптимальный вариант в первом примере — это выбрать первое блюдо номер \(2\), второе номер \(1\), напиток номер \(2\) и десерт номер \(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
|
26
|
|
2
|
1 1 1 1
1
1
1
1
1
1 1
0
0
|
-1
|