{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWould you want to fight against bears riding horses? Me neither.\u003c/p\u003e\u003cp\u003eLimak is a grizzly bear. He is general of the dreadful army of Bearland. The most important part of an army is cavalry of course.\u003c/p\u003e\u003cp\u003eCavalry of Bearland consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e warriors and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e horses. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th warrior has strength \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th horse has strength \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Warrior together with his horse is called a unit. Strength of a unit is equal to multiplied strengths of warrior and horse. Total strength of cavalry is equal to sum of strengths of all \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e units. Good assignment of warriors and horses makes cavalry truly powerful.\u003c/p\u003e\u003cp\u003eInitially, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th warrior has \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th horse. You are given \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e queries. In each query two warriors swap their horses with each other.\u003c/p\u003e\u003cp\u003eGeneral Limak must be ready for every possible situation. What if warriors weren\u0027t allowed to ride their own horses? After each query find the maximum possible strength of cavalry if we consider assignments of all warriors to all horses that no warrior is assigned to his own horse (it can be proven that for \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e ≥ 2\u003c/span\u003e there is always at least one correct assignment).\u003c/p\u003e\u003cp\u003eNote that we can\u0027t leave a warrior without a horse.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two space-separated integers, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 30 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 10 000\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e space-separated integers, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ew\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e) — strengths of warriors.\u003c/p\u003e\u003cp\u003eThe third line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e space-separated integers, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eh\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e) — strengths of horses.\u003c/p\u003e\u003cp\u003eNext \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines describe queries. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th of them contains two space-separated integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e, \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e), indices of warriors who swap their horses with each other.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines with answers to queries. In \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line print the maximum possible strength of cavalry after first \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e queries.\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 2\n1 10 100 1000\n3 7 2 5\n2 4\n2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5732\n7532\n\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\u003e3 3\n7 11 5\n3 2 1\n1 2\n1 3\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e44\n48\n52\n\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\u003e7 4\n1 2 4 8 16 32 64\n87 40 77 29 50 11 18\n1 5\n2 7\n6 2\n5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9315\n9308\n9315\n9315\n\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\u003eClarification for the first sample:\u003c/p\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eWarriors:\u0026nbsp;1\u0026nbsp;10\u0026nbsp;100\u0026nbsp;1000\u003c/span\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003eHorses:\u0026nbsp;\u0026nbsp;\u0026nbsp;3\u0026nbsp;\u0026nbsp;7\u0026nbsp;\u0026nbsp;2\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;5\u0026nbsp;\u003c/span\u003e \u003c/p\u003e\u003c/center\u003e\u003cp\u003eAfter first query situation looks like the following:\u003c/p\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eWarriors:\u0026nbsp;1\u0026nbsp;10\u0026nbsp;100\u0026nbsp;1000\u003c/span\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003eHorses:\u0026nbsp;\u0026nbsp;\u0026nbsp;3\u0026nbsp;\u0026nbsp;5\u0026nbsp;\u0026nbsp;2\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;7\u0026nbsp;\u003c/span\u003e \u003c/p\u003e\u003c/center\u003e\u003cp\u003eWe can get \u003cspan class\u003d\"tex-span\"\u003e1·2 + 10·3 + 100·7 + 1000·5 \u003d 5732\u003c/span\u003e (note that no hussar takes his own horse in this assignment).\u003c/p\u003e\u003cp\u003eAfter second query we get back to initial situation and optimal assignment is \u003cspan class\u003d\"tex-span\"\u003e1·2 + 10·3 + 100·5 + 1000·7 \u003d 7532\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eClarification for the second sample. After first query:\u003c/p\u003e\u003ccenter\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eWarriors:\u0026nbsp;\u0026nbsp;7\u0026nbsp;11\u0026nbsp;5\u003c/span\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-tt\"\u003eHorses:\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;2\u0026nbsp;\u0026nbsp;3\u0026nbsp;1\u003c/span\u003e \u003c/p\u003e\u003c/center\u003e\u003cp\u003eOptimal assignment is \u003cspan class\u003d\"tex-span\"\u003e7·1 + 11·2 + 5·3 \u003d 44\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThen after second query \u003cspan class\u003d\"tex-span\"\u003e7·3 + 11·2 + 5·1 \u003d 48\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eFinally \u003cspan class\u003d\"tex-span\"\u003e7·2 + 11·3 + 5·1 \u003d 52\u003c/span\u003e.\u003c/p\u003e"}}]}