DCEPC501 - Save Thy Toys


Leonard is very fond of buying rare and expensive science fiction toys. He keeps his collection in a sequential order of the date on which the toy was bought in a special closet so that his roomie Sheldon never gets hold of his toys. But because of his bad luck Leonard once loses a bet to Sheldon and Sheldon demands a share Leonard’s toys. Since Leonard doesn’t want to loose much money, he decides upon a strategy to reduce his loss to minimum.

Leonard, beginning from the first toy in his closet will pick some toys, say "x" toys in sequence. Sheldon will then pick the next "x" toys (Note that Sheldon picks equal no. of toys as picked by Leonard in his move unless the remaining toys are less than "x". In that case he picks all of the remaining). This will keep going on till no more toys are left in the closet for Leonard to pick. You are given the sequence of toys with their price. Help Leonard in maximizing the total price of all toys he picks.

Leonard in his each turn can either pick only 1 or 2 or 3 toys ("x" described above can take value either 1, 2 or 3).

Input

First line specifies T, the number of test cases.

Each test case contains N in the first line. Second line contains N integers as described above.

Output

Output 1 line for each test case giving the maximum possible value of the total sum of all toys Leonard picks.

Constraints

1<=T<=10

1<=N<=100000

1<=Price of toys<=1000000

Example

Input:
2
4
5 4 3 2
6
10 8 7 11 15 20

Output:
12
53

Explanation:

In 1st case, Leonard picks 3 toys in his first move with value 5,4,3 and Sheldon has no choice but to pick the last.
In 2nd case, Leonard picks 10, 8. Then Sheldon picks 7,11. And then Leonard picks the rest.


hide comments
SanchitK: 2013-12-18 18:39:32

does Lenord gets to change the number of toys he pics in each turn,or is the x constant for a given test case,
say can he pick 1,2,2 in his turns,or he has to pick 2,2,2 only(if possible)
@dce coders pls give more test cases

Last edit: 2013-12-18 18:41:37
Sameer: 2013-12-17 22:22:43

@Kevin Sebastian--> YES

Simes: 2013-10-17 19:12:42

Can Free Pascal be allowed please?

Siddharth Agarwal: 2013-09-11 22:25:47

after wasting 4 hrs in solving TLE, used scanf instead of cin and got ac .

Kevin Sebastian: 2013-08-26 09:25:34

this can be solved in O(N) TIME RIGHT?

Krishna Gadia: 2013-07-17 08:20:47

does Lenord gets to change the number of toys he pics in each turn,or is the x constant for a given test case,
say can he pick 1,2,2 in his turns,or he has to pick 2,2,2 only(if possible)

Charu: 2013-07-16 14:43:47

@DCE coders more test cases plz..Getting WA agin and again

Last edit: 2013-07-18 12:23:37
technophyle: 2013-06-26 04:14:53

use FAST I/O or scanf in C/C++

tainic: 2013-04-06 21:46:21

my solution looks correct, solves the sample test cases, but gets WA.

dce coders can you please verify and post some tricky test cases (if any?)

---

update: my solution was correct but I was using just "long" which is guaranteed to be at least 32 bits in size: http://en.wikipedia.org/wiki/C_data_types (contrary to Java); I switched to long long and got AC :)

oh C...

Last edit: 2013-04-07 20:44:29
Meraj Ahmed: 2012-10-20 05:51:19

ny special cases?? i m getting WA even though i thnk my solution is correct....DCE coder ??


Added by:dce coders
Date:2012-04-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem