{"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\nAkiba is a dangerous country since a bloodsucker living there. Sometimes the bloodsucker will appear and kill everyone who isn\u0027t at his hometown. One day, a brave person named CC finds a treasure map, and he wants to get as much as possible.\n\u003c/p\u003e\n\u003cp\u003e\nAkiba consists of \u003ci\u003en\u003c/i\u003e towns and \u003ci\u003en-1\u003c/i\u003e roads. There is a way from each town to any other. Each town contains some treasure values \u003ci\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e. CC starts from town \u003ci\u003ek\u003c/i\u003e(his hometown), at day 0. After \u003ci\u003em\u003c/i\u003e days, the bloodsucker will appear and CC would be killed if he hasn\u0027t been back yet, it means CC has \u003ci\u003em\u003c/i\u003e days for hunting the treasure at most. It takes CC \u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e days to move from one town to another neighbour town.(Two towns called neighbour if they are the endpoint of one road.) You can assume CC will get the treasure immediately as he arrives at that town. CC wants to obtain as much value as possible, keeping him alive at the same time.\n\u003c/p\u003e\n\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\n\u003cp\u003e\nThere are multiple cases, about 50 cases.\u003cbr\u003e\nThe first line of each case contains an integer \u003ci\u003en\u003c/i\u003e, indicating there are \u003ci\u003en\u003c/i\u003e towns.\u003cbr\u003e\nThe following line describe the treasure\u0027s value in each town. \"\u003ci\u003eV\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003eV\u003csub\u003e2\u003c/sub\u003e\u003c/i\u003e ... \u003ci\u003eV\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e\". \u003ci\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e is the value of the treasure in \u003ci\u003ei\u003c/i\u003eth town. Each value is separated by one blank.\u003cbr\u003e\nThe next \u003ci\u003en-1\u003c/i\u003e lines describe the \u003ci\u003en-1\u003c/i\u003e roads in Akiba. \"\u003ci\u003ei\u003c/i\u003e \u003ci\u003ej\u003c/i\u003e \u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\" Means the \u003ci\u003ei\u003c/i\u003eth town and the \u003ci\u003ej\u003c/i\u003eth town are endpoints of that road. It takes \u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e days to get through this road.\u003cbr\u003e\nThe last line has two integer \u003ci\u003ek\u003c/i\u003e and \u003ci\u003em\u003c/i\u003e as described above.\n\u003c/p\u003e\n\n\u003cp\u003e\n1\u0026lt;\u003d\u003ci\u003en\u003c/i\u003e\u0026lt;\u003d100, 0\u0026lt;\u003d\u003ci\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e\u0026lt;\u003d1000 , 1\u0026lt;\u003d\u003ci\u003eT\u003csub\u003ei\u003c/sub\u003e\u0026lt;\u003d10\u003c/i\u003e\u003cbr\u003e\n1\u0026lt;\u003d\u003ci\u003ek\u003c/i\u003e\u0026lt;\u003d\u003ci\u003en\u003c/i\u003e, 1\u0026lt;\u003dm\u0026lt;\u003d200\u003cbr\u003e\nAll the inputs are integers.\n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\n\u003cp\u003e\nJust output the max value CC can get, and you should keep CC alive after \u003ci\u003em\u003c/i\u003e days.\n\u003c/p\u003e\n\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 3\n1 2 1\n1 2\n2\n1 3\n2 1 1\n2 1\n2\n3 3\n1 2 1\n2 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n3\n6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003e\nSample 1: CC can go to town \u003ci\u003e2\u003c/i\u003e and return at day 2.\u003cbr\u003e\nSample 2: CC can\u0027t come back within 1 day. So he can only take the treasure in his hometown.\u003cbr\u003e\nSample 3: CC only need 2 days to collect all the treasure.\n\u003c/p\u003e\n"}}]}