{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nWormhole is a kind of two-way tunnel between two planets which can make it possible to transport large amounts of resources without time. Of course, building Wormhole has lots of requirements, only some pairs of the planet can build Wormhole and it costs lots of money. Country G is a very big country which has a lot of planets. There are several resource planets in country G. One resource planet can provide for a factory, and a factory need a resource planet to provide resource. Due to various reasons, country G has build some factories in several planets without considering about resource planets. So it depends on Wormhole to transport resource if a factory can\u0027t get resource from local. It is your task to make a plan to build Wormholes which can make most factories run and use the least money in this case.\n\u003c/p\u003e\n\u003ch4\u003e\nInput\n\u003c/h4\u003e\n\u003cp\u003e\nThe input consist of multiple cases. For each test case, the first line contains an integer \u003ci\u003eN\u003c/i\u003e (0 \u0026lt; \u003ci\u003eN\u003c/i\u003e ≤ 200) which indicates the number of planets in country G. Then followed by \u003ci\u003eN\u003c/i\u003e lines, each line contains two integers \u003ci\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e .\u003ci\u003eP\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the number of factories in planet i, if \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u003d1, planet i is a resource planet; if \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e \u003d0, planet i isn\u0027t a resource planet. At most of 4 planets have factories and at most of 4 planets are resource planets. The next line contains an integer \u003ci\u003eM\u003c/i\u003e (0 \u0026lt; \u003ci\u003eM\u003c/i\u003e ≤ 5000) which indicates the number of pairs of planet which can build Wormhole. Then followed by M lines, each line contains three integers \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, which indicate building Wormhole between planet \u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and planet \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e costs \u003ci\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e.\n\u003c/p\u003e\n\u003ch4\u003e\nOutput\n\u003c/h4\u003e\n\u003cp\u003e\nThe output contains one line per case. It contains the maximum of factories that can get resource and the the minimum of money when the maximum of factories that can get resource.\n\u003c/p\u003e\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e2\n1 0\n0 1\n1\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n"}}]}