{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThere are $$$n$$$ cities in the country. \u003c/p\u003e\u003cp\u003eTwo 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.\u003c/p\u003e\u003cp\u003eEach 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: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$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). \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFind out the maximum revenue that can be gained while fulfilling all demands of both candidates, or print \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e if it is not possible to do.\u003c/p\u003e\u003cp\u003eIt is additionally guaranteed, that each candidate has specified the port demands for the capital of his choice.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \\le n \\le 500$$$, $$$1 \\le x, y \\le n$$$)\u0026nbsp;— the number of cities, the capital of the first candidate and the capital of the second candidate respectively.\u003c/p\u003e\u003cp\u003eNext line contains integers $$$a_1, a_2, \\ldots, a_n$$$ ($$$1 \\le a_i \\le 100\\,000$$$)\u0026nbsp;— the revenue gained if the port is constructed in the corresponding city.\u003c/p\u003e\u003cp\u003eEach 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.\u003c/p\u003e\u003cp\u003eEach of the next $$$n - 1$$$ lines contains integers $$$u\u0027_i$$$ and $$$v\u0027_i$$$ ($$$1 \\le u\u0027_i, v\u0027_i \\le n$$$, $$$u\u0027_i \\ne v\u0027_i$$$), denoting edges between cities in the tree of the second candidate.\u003c/p\u003e\u003cp\u003eNext line contains an integer $$$q_1$$$ ($$$1 \\le q_1 \\le n$$$), denoting the number of demands of the first candidate.\u003c/p\u003e\u003cp\u003eEach of the next $$$q_1$$$ lines contains two integers $$$k$$$ and $$$x$$$ ($$$1 \\le k \\le n$$$, $$$1 \\le x \\le n$$$)\u0026nbsp;— the city number and the number of ports in its subtree.\u003c/p\u003e\u003cp\u003eNext line contains an integer $$$q_2$$$ ($$$1 \\le q_2 \\le n$$$), denoting the number of demands of the second candidate.\u003c/p\u003e\u003cp\u003eEach of the next $$$q_2$$$ lines contain two integers $$$k$$$ and $$$x$$$ ($$$1 \\le k \\le n$$$, $$$1 \\le x \\le n$$$)\u0026nbsp;— the city number and the number of ports in its subtree.\u003c/p\u003e\u003cp\u003eIt 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint exactly one integer\u0026nbsp;— the maximum possible revenue that can be gained, while satisfying demands of both candidates, or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e if it is not possible to satisfy all of the demands.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 1 2\n1 2 3 4\n1 2\n1 3\n3 4\n1 2\n2 3\n1 4\n2\n1 3\n4 1\n1\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 1 1\n3 99 99 100 2\n1 2\n1 3\n3 4\n3 5\n1 3\n1 2\n2 4\n2 5\n2\n1 2\n3 1\n2\n1 2\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e198\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 1 2\n1 2 3 4\n1 2\n1 3\n3 4\n2 1\n2 4\n4 3\n1\n1 4\n2\n4 1\n2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn 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 \u003d 9$$$.\u003c/p\u003e\u003cp\u003eIn 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 \u003d 198$$$. \u003c/p\u003e\u003cp\u003eIn 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 \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e.\u003c/p\u003e"}}]}