Politics

Description:

Input:

The first line contains integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 500$$$, $$$1 \le x, y \le n$$$) — the number of cities, the capital of the first candidate and the capital of the second candidate respectively.

Next line contains integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100\,000$$$) — the revenue gained if the port is constructed in the corresponding city.

Each of the next $$$n - 1$$$ lines contains integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), denoting edges between cities in the tree of the first candidate.

Each of the next $$$n - 1$$$ lines contains integers $$$u'_i$$$ and $$$v'_i$$$ ($$$1 \le u'_i, v'_i \le n$$$, $$$u'_i \ne v'_i$$$), denoting edges between cities in the tree of the second candidate.

Next line contains an integer $$$q_1$$$ ($$$1 \le q_1 \le n$$$), denoting the number of demands of the first candidate.

Each of the next $$$q_1$$$ lines contains two integers $$$k$$$ and $$$x$$$ ($$$1 \le k \le n$$$, $$$1 \le x \le n$$$) — the city number and the number of ports in its subtree.

Next line contains an integer $$$q_2$$$ ($$$1 \le q_2 \le n$$$), denoting the number of demands of the second candidate.

Each of the next $$$q_2$$$ lines contain two integers $$$k$$$ and $$$x$$$ ($$$1 \le k \le n$$$, $$$1 \le x \le n$$$) — the city number and the number of ports in its subtree.

It is guaranteed, that given edges correspond to valid trees, each candidate has given demand about each city at most once and that each candidate has specified the port demands for the capital of his choice. That is, the city $$$x$$$ is always given in demands of the first candidate and city $$$y$$$ is always given in the demands of the second candidate.

Output:

Print exactly one integer — the maximum possible revenue that can be gained, while satisfying demands of both candidates, or -1 if it is not possible to satisfy all of the demands.

Sample Input:

4 1 2
1 2 3 4
1 2
1 3
3 4
1 2
2 3
1 4
2
1 3
4 1
1
2 3

Sample Output:

9

Sample Input:

5 1 1
3 99 99 100 2
1 2
1 3
3 4
3 5
1 3
1 2
2 4
2 5
2
1 2
3 1
2
1 2
2 1

Sample Output:

198

Sample Input:

4 1 2
1 2 3 4
1 2
1 3
3 4
2 1
2 4
4 3
1
1 4
2
4 1
2 4

Sample Output:

-1

Note:

In the first example, it is optimal to build ports in cities $$$2$$$, $$$3$$$ and $$$4$$$, which fulfills all demands of both candidates and gives revenue equal to $$$2 + 3 + 4 = 9$$$.

In the second example, it is optimal to build ports in cities $$$2$$$ and $$$3$$$, which fulfills all demands of both candidates and gives revenue equal to $$$99 + 99 = 198$$$.

In the third example, it is not possible to build ports in such way, that all demands of both candidates are specified, hence the answer is -1.