TMSUM - The Maximize Sum

no tags 

You are given a set S of n elements. Do you know how many subsets the set has? It is 2^n where n is the number of elements in S.

For example, consider a set S of 3 elements. S= {1, 2, 3} so S has 2^3=8 subsets. They are {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}, {}. Here {} is empty set.

In 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}.

Find 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.

For example consider a set S= {1, 2, 3, 4, 5, 6}. So the subsets of S having at most 2 elements excluding 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}.

Now we can take subsets of {5,6}, {4,3} and {1,2} which contains all 6 elements of S then total sum  will be = (5*6)+(4*3)+(1*2) = 44. On the other hand if we take subsets of {5, 6}, {4, 3} and {1} & {2} then total sum will be= (5*6) + (4*3) +1+2=45 which is greater than the previous one.

Input

The 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 n — the number of distinct elements in the given set S. The second line contains n integers si (i=1,2,….., n) — the elements of the S.

Output

In a single line, output the maximum sum.

Constraints

  • 1 <= T <= 100
  • 1 <= n <= 100
  • -10000 <= si <= 10000

Example

Input:
2
6
1 2 3 4 5 6
3
1 2 3

Output:
45
7

hide comments
adityaghosh96: 2017-06-21 17:04:49

adhoc

akt_1998: 2017-06-21 16:41:38

adhoc ;)

aman_9899: 2017-06-21 11:37:55

dp...

Siddharth Singh: 2016-06-09 15:19:03

A very peculiar Corner Case Costed Me 3-4 WA's
Very Beautifull Question Though :)

ALi Ibrahim: 2016-05-19 21:15:05

@Divyaanand Sinha
Yes, they are all distinct.

ALi Ibrahim: 2016-05-19 21:13:00

nice problem :D

Divyaanand Sinha: 2016-05-18 18:43:57

are all the elements of the set distinct?

Last edit: 2016-05-18 20:42:18
poojan : 2016-05-16 04:46:52

1 test case :
input :
1
3
-1 0 1
output:
1

aditya730: 2016-04-28 13:19:38

I think one of the sample test cases gives way too much hint.


Added by:Akid Sultan
Date:2016-04-27
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem. Used in NHSPC 2016 Final Round. More about NHSPC: http://www.nhspc.org/