题目描述

Bessie 参加一个跑步比赛，比赛路线分为 \(n\) 段，其中第 \(i\) 段的分数为 \(a_i\)。在每段路上，她可以选择正常跑步、冲刺或慢走，每种方式得分不同：
\(1.\) 跑步，可以得 \(a_i\) 分；
\(2.\) 冲刺，可以得 \(a_i×2\) 分，但是下一段就只能慢走了；
\(3.\) 慢走，得分为 \(0\)。
编程计算 Bessie 整个比赛得分的最大值。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 10^5)\)，第二行为 \(n\) 个正整数 \(a_i(≤10^4)\)。

输出格式

对于每组数据，输出比赛的最大分值。

样例1

输入样例1

1
4
1 2 3 4

输出样例1

14

样例解释

第 \(1,2,3\) 段正常跑步，第 \(4\) 段冲刺，得分为 \(1+2+3+4+4=14\) 分。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("race.in","r",stdin);
freopen("race.out","w",stdout);