MAIN72 - Subset sum


You are given an array of N integers. Now you want to find the sum of all those integers which can be expressed as the sum of at least one subset of the given array.

Input

First line contains T the number of test case. then T test cases follow, first line of each test case contains N (1 ≤ N ≤ 100) the number of integers, next line contains N integers, each of them is between 0 and 1000 (inclusive).  

Output

For each test case print the answer in a new line.

Example

Input:
2
2
0 1
3
2 3 2

Output:
1
21

hide comments
jaikishan: 2015-06-18 00:07:47

good problem
worth the time

Last edit: 2015-06-18 00:08:43
i_am_looser: 2015-05-30 08:31:08

2 tle 2 wa but finally done using set.....stl rocks....

Anirudh Gupta: 2015-05-27 06:26:28

sigsegv on spoj but its running fyn on spoj.....plz help :(

Sandeep Singh: 2015-05-21 20:51:36

My First DP!! :)

Mensud Beèar: 2015-04-17 13:46:04

šaša :)

Anchrondite: 2015-03-29 07:50:19

Why using map gave me three TLE?While array done it in single shot.

Richa Jain: 2014-09-01 19:35:48

recurr+memo --> TLE
Bottom-up -->AC
Declare the array as static
my 50th :)

shantanu: 2014-08-10 23:24:27

Sigsegv on spoj. running fine on ideone. help?

Last edit: 2014-08-11 17:08:05
Muhammad Rifayat Samee (Sanzee): 2014-06-04 00:24:13

@chayan ghosh : you can use Dynamic Programming :). you can find the solution in O(N*S) where S is the summation of all the array elements. which actually is the highest possible subset sum that can be achieved.

Kousik Kumar: 2013-09-12 08:54:50

Brilliant problem! So deceiving :)


Added by:Mahesh Chandra Sharma
Date:2011-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA main contest #7