E. Политика
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране есть $$$n$$$ городов.

Два кандидата борются за пост президента страны. Выборы состоятся в скором будущем и оба кандидата уже спланировали как они собираются соединить города дорогами. Каждый из планов соединяет города используя ровно $$$n - 1$$$ дорогу. Иначе говоря, каждый план представляет из себя дерево. Оба кандидата также выбрали предлагаемую столицу среди $$$n$$$ городов ($$$x$$$ у первого кандидата, и $$$y$$$ у второго), которая может как совпадать, так и нет.

В каждом городе можно построить порт (в одном городе можно построить не более одного порта). Порт, построенный в $$$i$$$-м городе принесёт $$$a_i$$$ денег. Однако, у каждого кандидата есть свои специфичные требования, выглядящие следующим образом:

  • $$$k$$$ $$$x$$$, что означает, что кандидат хочет построить ровно $$$x$$$ портов в поддереве вершины $$$k$$$ (дерево подвешено за столицу, которую выбрал этот кандидат).

Выясните, какую наибольшую выручку можно получить, удовлетворив требованиям обоих кандидатов, или выведите -1, если это невозможно сделать.

Дополнительно гарантируется, что каждый из кандидатов указал свои специфичные требования относительно своей столицы.

Входные данные

Первая строка содержит целые числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$1 \le n \le 500$$$, $$$1 \le x, y \le 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$$$) — номер города и количество портов в его поддереве.

Следующая строка содержит одно целое число $$$q_2$$$ ($$$1 \le q_2 \le n$$$), обозначающее количество специфичных требований второго кандидата.

Каждая из следующих $$$q_2$$$ строк содержит целые числа $$$k$$$ и $$$x$$$ ($$$1 \le k \le n$$$, $$$1 \le x \le n$$$) — номер города и количество портов в его поддереве.

Гарантируется, что заданные рёбра задаут корректные деревья, что каждый кандидат задал специфичное требование про каждый город не более одного раза и что каждый кадидат задал специфичные требования относительно своей столицы. То есть город $$$x$$$ есть в требованиях первого кандидата, а город $$$y$$$ — в требованиях второго.

Выходные данные

Выведите ровно одно целое число — наибольшую прибыль, которую можно получить, удовлетворив специфичным требованиям обоих кандидатов или -1, если это сделать невозможно.

Примеры
Входные данные
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
Выходные данные
9
Входные данные
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
Выходные данные
198
Входные данные
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
Выходные данные
-1
Примечание

В первом примере оптимально построить порты в городах $$$2$$$, $$$3$$$ и $$$4$$$, что удовлетворяет всем требованиям обоих кандидатов и приносит прибыль $$$2 + 3 + 4 = 9$$$.

Во втором примере оптимально построить порты в городах $$$2$$$ и $$$3$$$, что удовлетворяет всем требованиям обоих кандидатов и приносит прибыль $$$99 + 99 = 198$$$.

В третьем примере не возможно построить порты таким образом, чтобы удовлетворить всем требованиям, а значит ответ -1.