问题 B：棋盘游戏
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：4
解决：2
题目描述
Carol 有一个条形棋盘，棋盘上依次放置了 $n$ 个棋子，从左到右标号为 $1, 2, \dots, n$，每个棋子上标有一个整数 $a_i$。Carol 可以按照如下规则进行操作来获得得分，初始得分为 0。
每次，Carol 可以执行以下三种操作之一：
1. **选择奇数列的棋子**: 选择棋盘从左往右数第 $i$ 列 (即奇数列) 的棋子，将该棋子移除并将其值加到当前得分上。
2. **选择偶数列的棋子**: 选择棋盘从左往右数第 $i$ 列 (即偶数列) 的棋子，将该棋子移除，但分数不会发生变化。
3. **终止游戏**: Carol 可以在任何时刻结束游戏，无需移除棋盘上所有棋子。
每次移除棋子后，棋盘上的其余棋子会重新按从左到右的顺序排列并重新编号。Carol 的目标是通过合理操作，使游戏结束时的得分最大化，请你帮助他求出这个最大得分。
每次，Carol 可以执行以下三种操作之一：
1. **选择奇数列的棋子**: 选择棋盘从左往右数第 $i$ 列 (即奇数列) 的棋子，将该棋子移除并将其值加到当前得分上。
2. **选择偶数列的棋子**: 选择棋盘从左往右数第 $i$ 列 (即偶数列) 的棋子，将该棋子移除，但分数不会发生变化。
3. **终止游戏**: Carol 可以在任何时刻结束游戏，无需移除棋盘上所有棋子。
每次移除棋子后，棋盘上的其余棋子会重新按从左到右的顺序排列并重新编号。Carol 的目标是通过合理操作，使游戏结束时的得分最大化，请你帮助他求出这个最大得分。
输入
第一行一个整数 $T$ 表示数据组数。
对于每组数据:
第一行一个正整数 $n$。
对于每组数据:
第一行一个正整数 $n$。
第二行 $n$ 个整数 $a_{1 \sim n}$。
$1\le T\le 10^4, 1\le n,\sum n\le 2\times 10^5,-10^9\le a_i\le 10^9$
输出
对于每种数据，输出一行一个整数表示答案
样例输入-1 复制
4
4
-4 1 -3 5
4
1 -2 3 -4
3
-1 3 -5
1
-1样例输出-1 复制
5
4
2
0