WEIGHT - Weighted Sum

no tags 

You are given N integers, A[1] to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :

  1. Each weight should be an positive integer.
  2. W[1] = 1
  3. W[i] should be in the range [2, W[i-1] + 1] for i > 1

Weighted sum is defined as S = A[1] * W[1] + A[2] * W[2] + ... + A[N] * W[N]

Input

There are multiple test cases.
First line contains the number of test cases
Each test case consists of a single line containing N.
This is followed by N lines, each containing A[i]

Output

For each test case, output one line - the maximum weighted sum.

Example

Input:
1
4
1
2
3
-4
Output: 6

Explanation

The weights are 1, 2, 3, 2.

Constraints

N <= 10^6
| A[i] | <= 10^6
Total number of test cases is around 10.


hide comments
Ivan Sto¹iæ: 2014-05-05 04:02:19

Nice one!
Fast I/O is recommended.

Bhavik: 2013-12-20 15:35:11

all test cases given(also in comments) are working fine,,,,even took long long but stil WA!!!!
any tricky ones still...or something else??

AC..finally

Last edit: 2014-01-02 21:28:27
ROHIT RAWAT: 2013-11-01 08:00:57

program is working for sample test case and the cases provided by Albert Chen. Still getting WA.
use long long int for all variables(c/c++)

AC after 10 WA. try this too(apart from cases by Albert Chen).
-1 -2 -3 10 -10

Last edit: 2013-11-02 06:11:15
Srijan Khare: 2013-05-30 12:35:35

nice problem...

ANKIT KUMAR SRIVASTAVA: 2013-03-22 13:38:22

finally i did it,think as AD-HOC friends

Akshay Kumar: 2012-12-20 20:41:47

use long long int for number of test cases and number of elements,got 3 WA coz of that

Abhik Mondal: 2012-07-02 12:32:11

any reason for a seg fault?

Piyush Kapoor: 2012-06-15 20:09:55

nice problem!! :D

Sahil Garg: 2012-05-11 06:34:24

working for the above test case.. still WA

yo :P: 2012-03-31 22:07:37

thnx aman kumar :)


Added by:Kunal Jain
Date:2011-02-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 11