CF1487E.Cheap Dinner

Ivan wants to have a good dinner. A good dinner should consist of a first course, a second course, a drink, and a dessert.

There are $n_1$ different types of first courses Ivan can buy (the $i$-th of them costs $a_i$ coins), $n_2$ different types of second courses (the $i$-th of them costs $b_i$ coins), $n_3$ different types of drinks (the $i$-th of them costs $c_i$ coins) and $n_4$ different types of desserts (the $i$-th of them costs $d_i$ coins).

Some dishes don't go well with each other. There are $m_1$ pairs of first courses and second courses that don't go well with each other, $m_2$ pairs of second courses and drinks, and $m_3$ pairs of drinks and desserts that don't go well with each other.

Ivan wants to buy exactly one first course, one second course, one drink, and one dessert so that they go well with each other, and the total cost of the dinner is the minimum possible. Help him to find the cheapest dinner option!

伊万想吃一顿丰盛的晚餐。一顿丰盛的晚餐应包含一道头盘、一道主菜、一杯饮品和一份甜点。

可供选择的头盘有 $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$ 对不搭配的饮品与甜点组合。

伊万希望恰好选购一道头盘、一道主菜、一杯饮品和一份甜点，且所选四者彼此搭配，同时使整顿晚餐的总花费最低。请帮他找出最便宜的晚餐方案！

The first line contains four integers $n_1$, $n_2$, $n_3$ and $n_4$ ($1 \le n_i \le 150000$) — the number of types of first courses, second courses, drinks and desserts, respectively.

Then four lines follow. The first line contains $n_1$ integers $a_1, a_2, \dots, a_{n_1}$ ($1 \le a_i \le 10^8$), where $a_i$ is the cost of the $i$-th type of first course. Three next lines denote the costs of second courses, drinks, and desserts in the same way ($1 \le b_i, c_i, d_i \le 10^8$).

The next line contains one integer $m_1$ ($0 \le m_1 \le 200000$) — the number of pairs of first and second courses that don't go well with each other. Each of the next $m_1$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n_1$; $1 \le y_i \le n_2$) denoting that the first course number $x_i$ doesn't go well with the second course number $y_i$. All these pairs are different.

The block of pairs of second dishes and drinks that don't go well with each other is given in the same format. The same for pairs of drinks and desserts that don't go well with each other ($0 \le m_2, m_3 \le 200000$).

第一行包含四个整数 $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$）。

If it's impossible to choose a first course, a second course, a drink, and a dessert so that they go well with each other, print $-1$. Otherwise, print one integer — the minimum total cost of the dinner.

如果无法选择一道主菜、一道副菜、一种饮品和一份甜点，使得它们彼此搭配得当，则输出 $-1$；否则，输出一个整数——晚餐的最低总费用。

The best option in the first example is to take the first course $2$, the second course $1$, the drink $2$ and the dessert $1$.

In the second example, the only pair of the first course and the second course is bad, so it's impossible to have dinner.

第一个样例中的最优选择是：第一道菜选 $2$，第二道菜选 $1$，饮料选 $2$，甜点选 $1$。

第二个样例中，唯一的一对第一道菜与第二道菜的组合是不合法的，因此无法完成晚餐。