В стране есть \(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, если это сделать невозможно.
Примечание
В первом примере оптимально построить порты в городах \(2\), \(3\) и \(4\), что удовлетворяет всем требованиям обоих кандидатов и приносит прибыль \(2 + 3 + 4 = 9\).
Во втором примере оптимально построить порты в городах \(2\) и \(3\), что удовлетворяет всем требованиям обоих кандидатов и приносит прибыль \(99 + 99 = 198\).
В третьем примере не возможно построить порты таким образом, чтобы удовлетворить всем требованиям, а значит ответ -1.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|
|
3
|
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
|