CF1061E.Politics

There are $n$ cities in the country.

Two candidates are fighting for the post of the President. The elections are set in the future, and both candidates have already planned how they are going to connect the cities with roads. Both plans will connect all cities using $n - 1$ roads only. That is, each plan can be viewed as a tree. Both of the candidates had also specified their choice of the capital among $n$ cities ($x$ for the first candidate and $y$ for the second candidate), which may or may not be same.

Each city has a potential of building a port (one city can have at most one port). Building a port in $i$-th city brings $a_i$ amount of money. However, each candidate has his specific demands. The demands are of the form:

• $k$ $x$, which means that the candidate wants to build exactly $x$ ports in the subtree of the $k$-th city of his tree (the tree is rooted at the capital of his choice).

Find out the maximum revenue that can be gained while fulfilling all demands of both candidates, or print -1 if it is not possible to do.

It is additionally guaranteed, that each candidate has specified the port demands for the capital of his choice.

该国共有 $n$ 座城市。

两名候选人正在竞选总统职位。选举将在未来举行，且两名候选人均已规划好如何用道路连接所有城市。两种方案均仅使用 $n - 1$ 条道路将全部城市连通，即每种方案均可视为一棵树。此外，两名候选人均已在 $n$ 座城市中各自选定首都（第一位候选人选的是城市 $x$，第二位候选人选的是城市 $y$），二者可能相同，也可能不同。

每座城市均具备建设港口的潜力（每座城市最多建设一座港口）。在第 $i$ 座城市建设港口可带来 $a_i$ 的收益。然而，每名候选人均有其特定的要求，形式如下：

• $k$ $x$：表示该候选人要求在其树结构中以第 $k$ 座城市为根的子树内恰好建设 $x$ 座港口（该树以该候选人所选的首都为根）。

请计算在同时满足两名候选人所有要求的前提下，所能获得的最大总收益；若无法同时满足所有要求，则输出 -1。

额外保证：每名候选人所提出的所有港口建设要求中，必包含对其所选首都城市对应子树的要求。

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.

第一行包含三个整数 $n$、$x$ 和 $y$（$1 \le n \le 500$，$1 \le x, y \le n$），分别表示城市数量、第一位候选人的首都以及第二位候选人的首都。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 100\,000$），表示在对应城市建造港口所能获得的收益。

接下来的 $n - 1$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第一位候选人所对应的树中城市之间的边。

再接下来的 $n - 1$ 行每行包含两个整数 $u'_i$ 和 $v'_i$（$1 \le u'_i, v'_i \le n$，$u'_i \ne v'_i$），表示第二位候选人所对应的树中城市之间的边。

下一行包含一个整数 $q_1$（$1 \le q_1 \le n$），表示第一位候选人的需求条数。

接下来的 $q_1$ 行每行包含两个整数 $k$ 和 $x$（$1 \le k \le n$，$1 \le x \le n$），表示城市编号 $k$ 及其子树中需建造的港口数量。

下一行包含一个整数 $q_2$（$1 \le q_2 \le n$），表示第二位候选人的需求条数。

接下来的 $q_2$ 行每行包含两个整数 $k$ 和 $x$（$1 \le k \le n$，$1 \le x \le n$），表示城市编号 $k$ 及其子树中需建造的港口数量。

保证所给的边构成合法的树；每位候选人对每个城市的需求数至多出现一次；且每位候选人均已为其所选首都指定港口需求。即：城市 $x$ 总是出现在第一位候选人的需求中，城市 $y$ 总是出现在第二位候选人的需求中。

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.

输出一个整数——在满足两位候选人需求的前提下所能获得的最大收益；如果无法满足所有需求，则输出 $-1$。

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.

在第一个例子中，最优方案是在城市 $2$、$3$ 和 $4$ 建设港口，这能够满足两位候选人的全部需求，且获得的收益为 $2 + 3 + 4 = 9$。

在第二个例子中，最优方案是在城市 $2$ 和 $3$ 建设港口，这能够满足两位候选人的全部需求，且获得的收益为 $99 + 99 = 198$。

在第三个例子中，不存在一种建设港口的方式，使得两位候选人的全部需求均被满足，因此答案为 $-1$。