Cheap Dinner
Contest: Educational Codeforces Round 104 (Rated for Div. 2)
Difficulty rating: 2000
Tags: brute force, data structures, graphs, greedy, implementation, sortings, two pointers

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!

Input format:
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$$$).

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
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

Example output:
26

Example input:
1 1 1 1
1
1
1
1
1
1 1
0
0

Example output:
-1

Editorial:
The main solution is dynamic programming: let $$$dp_i$$$ for every possible dish $$$i$$$ be the minimum cost to assemble a prefix of a dinner ending with the dish $$$i$$$ (here, $$$i$$$ can be a dish of any type: first course, second course, drink, or dessert). Then, the answer to the problem is the minimum value among all desserts.
The number of transitions in this dynamic programming is too big, since, for example, when transitioning from first courses to second courses, we need to check $$$O(n_1 n_2$$$) options. To speed this up, we need some sort of data structure built over the values of $$$dp_i$$$ for all first courses $$$i$$$ that allows to recalculate $$$dp_j$$$ for a second course $$$j$$$ quickly. There are two main approaches to this:
• build any version of RMQ over the values of dynamic programming for the first courses. Then, when we want to calculate the answer for some second course $$$j$$$, sort all types of first courses which don't go well with it, and make several RMQ queries to find the minimum value over all non-forbidden first courses;
• store all values of $$$dp_i$$$ in a data structure that supports adding an element, deleting an element, and finding the minimum element (this DS should allow duplicate elements as well). When we want to calculate the answer for some second course $$$j$$$, remove all values of $$$dp_i$$$ corresponding to the first courses that don't go well with it from the data structure, query the minimum in it, and insert the removed elements back.
The same approach can be used to advance from second courses to drinks and from drinks to desserts (you can even use the same code in a for-loop with $$$3$$$ iterations, so the resulting solution is actually short and simple).