TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

一年一度的 IOICamp 正在如火如荼的舉行當中。正當學員們都在認真地聽課的時候,那位一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式的天才兒童殿壬正在回味他兩個月大的時候遭遇到的一個問題。

某些人可能會聽過,殿壬在一個月大的時候總是藉由計算一串數字當中有幾個「洞」來練習數數。在練習了一個月後(也就是殿壬兩個月大的時候)他開始探討「洞」的成因,也就是圍著洞的那個「環」。同時為了繼續練習數數,殿壬養成了一種新的興趣,就是在每個環上依序寫下很多數字。

然而殿壬的求知欲並不會因此而滿足。所以聰明的殿壬又想到了新的一種自我訓練的方法,也就是把所有在環上的數字加總起來。然而好巧不巧的,每當殿壬在進行這項訓練的時候,都會有不少的蝴蝶來干擾殿壬。具體來講,蝴蝶們會藉由把一些數字拿走來讓殿壬沒辦法把全部的數字加起來,而殿壬只能開始跟蝴蝶抗爭,也就是開始把一些數字搶在蝴蝶之前拿走,然後把這些數字加起來。依舊很巧合的,殿壬跟蝴蝶們雙方都會很想要最大化自己所拿走的所有數字的總和。但是因為蝴蝶不大,殿壬也不大(他才兩個月大而已),所以不論是蝴蝶還是殿壬,每次都只能拿走原本在環上的連續一個段落的數字。注意第一個數字與最後一個數字是相連的,且環在數字被拿走後不會接起來。此外,殿壬跟蝴蝶達成了一個協議(雖然不知道是怎麼達成的),也就是殿壬跟蝴蝶會輪流的把數字拿走,且至少要拿一個。不過因為蝴蝶有很多隻,所以每一次蝴蝶把數字拿走之後,蝴蝶的總數就會增加 $1$。又受限於體型的關係,殿壬一次最多可以把連續的 $7$ 個數字拿走,蝴蝶一次最多可以把連續的 $b$ 個數字拿走,其中 $b$ 是蝴蝶的數量。第一次輪到蝴蝶拿走數字的時候一共有一隻蝴蝶,並且殿壬會先開始將數字拿走。

不過為了知道殿壬究竟有沒有加錯,在殿壬跟蝴蝶協議的內容還有一個部分就是在環上的所有數字被取光之後,蝴蝶們必須跟殿壬說被牠們拿走的數字總和是多少。

現在,問題來了,請告訴殿壬,在遊戲結束的時候,在雙方都採取對自己最優的策略的情況之下,殿壬拿走的所有數字的總和加上蝴蝶拿走的所有數字的總和是多少?

Input Format

第一行有一個正整數$T$,代表總共有幾筆測試資料。
之後的每一筆測試資料會有兩行,第一行有一個正整數$N$代表環上所寫著的數字數量。
第二行會有 $N$ 個整數,依序代表寫在環上的數字。

  • $T \leq 20$
  • $N \leq 1000$
  • $|$ 寫在環上的數字 $| \leq 1000000000$

Output Format

請輸出 $T$ 行,其中第 $i$ 行代表第 $i$ 筆測試資料的答案。

Sample Input

1
7
1 1 1 1 1 1 1

Sample Output

7

Hints

是數字喔 > <

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144