{"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\r\nThere are \u003cvar\u003en\u003c/var\u003e individuals(2 \u0026lt;\u003d \u003cvar\u003en\u003c/var\u003e \u0026lt;\u003d 30000). Everyone has one or more friends. \r\nAnd everyone can contact all people by friend-relation. If two persons aren\u0027t friends, they also can contact by their friends.\r\nEach pair of friends have a friendship value \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e(1 \u0026lt;\u003d \u003cvar\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt;\u003d 50000).\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nFirstly, you will relieve some friend-relation. The rest of the friend-relation is the social net.\r\nThe net is unique in all test cases. In this net, everyone can contact all people by rest friend-relation.\r\nThe net has a minimum number of friend-relation. And the net has maximum sum of friendship value. We want to get the maximum sum.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nSecondly, everyone has an angry value \u003cvar\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e(1 \u0026lt;\u003d \u003cvar\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e \u0026lt;\u003d 100000).\r\nWe have \u003cvar\u003eq\u003c/var\u003e operations(1 \u0026lt;\u003d \u003cvar\u003eq\u003c/var\u003e \u0026lt;\u003d 30000): Person X wants to contact person Y, this operation merely has one sequence which describes the process.\r\nThe sequence consists of persons\u0027 angry value. The persons are on the process.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nWe suppose the sequence is \u003cvar\u003ec\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003ec\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003ec\u003csub\u003e3\u003c/sub\u003e\u003c/var\u003e, ... ,\u003cvar\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e. Here \u003cvar\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e means the angry value of the ith people in the sequence.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nWe attempt to find the maximum \u003cvar\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/var\u003e-\u003cvar\u003ec\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e (\u003cvar\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/var\u003e \u0026gt;\u003d \u003cvar\u003ec\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e, \u003cvar\u003ej\u003c/var\u003e \u0026lt;\u003d \u003cvar\u003ek\u003c/var\u003e).\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nExample:\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe sequence is 3(X), 4, 5, 6, 7, 5, 9, 4, 11(Y). The maximum \u003cvar\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/var\u003e-\u003cvar\u003ec\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e is 11-3\u003d8.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe sequence is 3(X), 4, 5, 6, 7, 5, 9, 2, 11(Y). The maximum \u003cvar\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/var\u003e-\u003cvar\u003ec\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e is 11-2\u003d9.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe sequence is 3(X), 10, 2, 5(Y). The maximum \u003cvar\u003ec\u003csub\u003ek\u003c/sub\u003e\u003c/var\u003e-\u003cvar\u003ec\u003csub\u003ej\u003c/sub\u003e\u003c/var\u003e is 10-3\u003d7.\r\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\u003cp\u003e\r\nThe input contains multiple test cases.\r\nEach test case begins with a line containing a single integer \u003cvar\u003en\u003c/var\u003e.\r\nThe following line contains \u003cvar\u003en\u003c/var\u003e integers \u003cvar\u003ebi\u003c/var\u003e.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe subsequent line describe the number of relations \u003cvar\u003em\u003c/var\u003e(\u003cvar\u003en\u003c/var\u003e \u0026lt;\u003d \u003cvar\u003em\u003c/var\u003e \u0026lt;\u003d 50000).\r\nThe next \u003cvar\u003em\u003c/var\u003e lines contain the information about relations: \u003cvar\u003ex\u003c/var\u003e, \u003cvar\u003ey\u003c/var\u003e, \u003cvar\u003eai\u003c/var\u003e. Their friendship value is \u003cvar\u003eai\u003c/var\u003e.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nAfterward gives \u003cvar\u003eq\u003c/var\u003e.\r\nThe next \u003cvar\u003eq\u003c/var\u003e lines contain the operations: \u003cvar\u003ex\u003c/var\u003e, \u003cvar\u003ey\u003c/var\u003e. person X wants to contact person Y.\r\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\r\n\u003cp\u003e\r\nFor each case, print maximum sum of friendship value of the net on the first line.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nThe next q lines contain the answers of every operations.\r\n\u003c/p\u003e\r\n\r\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\u003e\r\n6\r\n3 5 1 7 3 5\r\n7\r\n1 2 5\r\n1 3 6\r\n2 4 7\r\n2 5 8\r\n3 6 9\r\n4 5 1\r\n5 6 2\r\n5\r\n6 1\r\n6 2\r\n6 3\r\n6 4\r\n6 5\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\r\n35\r\n2\r\n4\r\n0\r\n6\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}