{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eYou are given a set S of n elements. Do you know how many subsets the set has? It is 2\u003csup\u003en\u003c/sup\u003e where n is the number of elements in S.\u003c/p\u003e\r\n\u003cp\u003eFor example, consider a set S of 3 elements. S \u003d {1, 2, 3} so S has 2\u003csup\u003e3\u003c/sup\u003e \u003d 8 subsets. They are {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, {1, 2, 3}, { }. Here { } is empty set.\u003c/p\u003e\r\n\u003cp\u003eIn the above example number of subsets of S having at most 2 elements excluding empty set are {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}.\u003c/p\u003e\r\n\u003cp\u003eFind subsets which have at most 2 elements excluding empty set in which each element of S must belong to a single a subset i.e. if we take subset for example {1} then we can’t take other subsets containing element 1. Now sum the product of the subsets containing 2 elements with the value of subsets containing single element. Your target will be maximizing this sum.\u003c/p\u003e\r\n\u003cp\u003eFor example consider a set S\u003d {1, 2, 3, 4, 5, 6}. So the subsets of S having at most 2 elements excluding the empty set are {1}, {2}, {3}, {4}, {5}, {6}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}.\u003c/p\u003e\r\n\u003cp\u003eNow we can take subsets of {5, 6}, {4, 3} and {1, 2} which contains all 6 elements of S then total sum\u0026nbsp; will be \u003d (5 * 6) + (4 * 3) + (1 * 2) \u003d 44. On the other hand if we take subsets of {5, 6}, {4, 3} and {1} and {2} then total sum will be (5 * 6) + (4 * 3) + 1 + 2 \u003d 45 which is greater than the previous one.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line of the input will be an integer T to represent the number of test cases. For each case there will be two lines. The first line contains integer\u0026nbsp;\u003cem\u003en\u003c/em\u003e\u0026nbsp;— the number of distinct elements in the given set S. The second line contains\u0026nbsp;\u003cem\u003en\u003c/em\u003e\u0026nbsp;integers\u0026nbsp;s\u003csub\u003ei\u003c/sub\u003e\u0026nbsp;(i \u003d 1, 2 ... n) — the elements of the S.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eIn a single line, output the maximum sum.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e1 ≤ T ≤ 100\u003c/li\u003e\r\n\u003cli\u003e1 ≤ n ≤ 100\u003c/li\u003e\r\n\u003cli\u003e-10000 ≤ s\u003csub\u003ei\u003c/sub\u003e ≤ 10000\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\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\r\n6\r\n1 2 3 4 5 6\r\n3\r\n1 2 3\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e45\r\n7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\n\u003c/div\u003e"}}]}