2017GCOI六年级第五题 积木（2.5）
说明
乔治喜欢玩积木。目前他有 N 块积木，编号为 1 到 N。所有积木的高度都是正整数，第 i 块积木高度是 H[i]。乔治喜欢用积木堆起尽可能高的塔。他堆积木的过程中，只需要同时满足如下三个规则：（1）积木必须堆放在同一个列中，一个搭在另一个上面。最终的塔的高度就是构成塔的所有积木的高度总和。
（2）塔中使用的积木的编号从底部到顶部必须是递增的。换句话说，每当乔治把积木 x 放在积木 y 的上面，必须要满足编号 x 大于 编号 y。
（3）乔治永远不会把高度是偶数的积木放置在高度是奇数的积木上面。
在满足上面的前提下，塔最高是多高？
输入格式
多组测试数据。第一行，一个整数 G，表示有 G 组测试数据。 1 <= G <= 5。
每组测试数据格式如下：
第 1 行，一个正整数 N。 2 <= N <= 50。
第 2 行， N 个正整数，空格分开，第 i 个整数就是编号为 i 的积木的高度 H[i]，1 <= H[i] <= 50。
输出格式
共 G 行，每行一个正整数。样例
提示
【样例输入2】
1
9
2 2 4 4 7 3 8 9 6
【样例输出2】
31