WEIGHT - Weighted Sum

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.


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

hide comments
2012-02-01 16:55:22 Albert Chen
@pvr_nrt I misunderstand your question... It's sort of DP, but not typical.

Last edit: 2012-02-01 19:55:47
2012-01-30 18:26:14 pvr_nrt
@Albert Chen is it DP ?

Last edit: 2012-01-30 18:28:50
2011-11-29 03:36:23 Albert Chen
I felt %^&* good when I figured it out...
Some more testcases:
1,2,-3,1,2-->10
1,1,1,-4,3-->7
1,2,-3,-4,10000-->49980

Last edit: 2011-11-29 04:41:01
2011-09-09 08:32:23 Chandan Giri
nice problem :)
2011-09-03 07:31:24 Gurpreet Singh
Yeah!! I have to analyse the cases for longgg time. nice and easy problem.
2011-06-29 13:55:30 akshay verma
more testcases please!!
2011-04-17 19:29:34 Garg Ankit
plzz provide more test cases..
getting WA :(
2011-04-14 10:23:46 el moatasem
I do it in O(n) in pyth and cpp
how come TLE
at least i should read the input at least O(n)
2011-02-17 08:57:28 vg88
what order recquire for this problem
2011-02-10 19:21:33 :D
That's a part of this problem, you have to answer it yourself. Don't try to guess lemats for the task!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.