Chef and the Feast

All submissions for this problem are available.
Read problems statements in Russian.
Chef has prepared a feast with N dishes for you. You like Chef's cooking, and so you want to eat all the dishes he has prepared for you. You are also given an array A of size N, where A_{i} represents the happiness you get by eating the ith dish.You will eat all the dishes in a series of steps. In each step, you pick a non empty subset of the remaining dishes and eat them. The happiness you get from eating these dishes is the size of the subset multiplied by the sum of the individual happiness from the dishes in the subset. You want to maximize the happiness you get from the entire feast, which is the sum of happiness in each step.
Input
The first line contains T, the number of test cases.
The first line of each test case contains a single integer N, denoting the number of dishes prepared by the Chef.
The second line of each test case contains contains N spaceseparated integers: A_{1}, A_{2}, ..., A_{N} denoting the happiness gained by eating the dishes.
Output
Output a single number denoting the maximum happiness you can get from the feast.
Constraints
 1 ≤ T ≤ 8
 1 ≤ N ≤ 10^{5}
 10^{8} ≤ A_{i} ≤ 10^{8}
Subtasks
 Subtask #1: A_{i} ≤ 0 (30 points)
 Subtask #2: Original Constraints (70 points)
Example 1
Input: 1 3 8 0 2 Output: 10
Example 2
Input: 1 3 1 2 3 Output: 18
Explanation
Example case 1. You can eat the first dish in the first step, the second dish in the second step and the third dish in the third step. total happiness = 1*(8) + 1*0 + 1*(2) = 10
Author:  neo1tech9_7 
Editorial  https://discuss.codechef.com/problems/NEO01 
Tags  easy, june17, neo1tech9_7 
Date Added:  13052017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 