{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e度度熊是他同时代中最伟大的数学家,一切数字都要听命于他。现在,又到了度度熊和他的数字仆人们玩排排坐游戏的时候了。游戏的规则十分简单,参与游戏的N个整数将会做成一排,他们将通过不断交换自己的位置,最终达到所有相邻两数乘积的和最大的目的,参与游戏的数字有整数也有负数。度度熊为了在他的数字仆人面前展现他的权威,他规定某些数字只能在坐固定的位置上,没有被度度熊限制的数字则可以自由地交换位置。\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"第一行一个整数$T$,表示$T$组数据。\u003cbr\u003e每组测试数据将以如下格式从标准输入读入:\u003cbr\u003e\u003cbr\u003e$N$\u003cbr\u003e\u003cbr\u003e$a_1 p_1$\u003cbr\u003e\u003cbr\u003e$a_2 p_2$\u003cbr\u003e\u003cbr\u003e: \u003cbr\u003e\u003cbr\u003e$a_N P_N$\u003cbr\u003e\u003cbr\u003e第一行,整数 $N (1 \\leq N \\leq 16)$,代表参与游戏的整数的个数。\u003cbr\u003e\u003cbr\u003e从第二行到第 $(N + 1)$ 行,每行两个整数,$a_{i} (-10000 \\leq a_{i} \\leq 10000)$、$p_{i} (p_{i} \u003d -1$ 或 $0 \\leq p_{i} \u0026lt; N)$,以空格分割。$a_{i}$代表参与游戏的数字的值,$p_{i}$代表度度熊为该数字指定的位置,如果$p_{i} \u003d -1$,代表该数字的位置不被限制。度度熊保证不会为两个数字指定相同的位置。"}},{"title":"Output","value":{"format":"HTML","content":"第一行输出:\"Case #i:\"。$i$代表第$i$组测试数据。\u003cbr\u003e\u003cbr\u003e第二行输出数字重新排列后最大的所有相邻两数乘积的和,即$max\\{a_1\\cdot a_2+a_2\\cdot a_3+......+a_{N-1}\\cdot a_N\\}$。"}},{"title":"Sample","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\u003e2\r\n6\r\n-1 0\r\n2 1\r\n-3 2\r\n4 3\r\n-5 4\r\n6 5\r\n5\r\n40 -1\r\n50 -1\r\n30 -1\r\n20 -1\r\n10 -1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\r\n-70\r\nCase #2:\r\n4600\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}