零食大作战

题面描述

今天是六一儿童节，班主任王老师组织了一场零食分享会。全班有 $N$ 位同学，每位同学都带了一些零食到学校。

对于每位同学，王老师规定分享过程如下：

1. 这位同学带来的零食被分成若干种，已知每种零食的数量。
2. 在分享开始前，可以任意重新安排零食的分享顺序。
3. 每一轮只能拿出 1 包 零食放到公共分享区。
4. 从第二轮开始，本轮拿出的零食种类必须与上一轮不同，也就是说，连续两轮不能分享同一种零食。
5. 如果某些零食无法在满足上述规则的情况下继续分享，可以将它们留到最后，不要求所有零食都必须被分享。

每位同学的分享过程彼此独立。

现在给出每位同学所带的各种零食数量，请你计算：在最优安排下，每位同学最多可以连续进行多少轮分享？

输入

第一行输入一个整数 $N$，表示同学人数。$(1\leq N\leq 100)$

接下来 $N$ 行，每行先输入一个整数 $M$，表示该同学带来的零食种类数，随后输入 $M$ 个整数 $a_1,a_2,\dots,a_M$，其中 $a_i$ 表示第 $i$ 种零食的数量。

$(1\leq M\leq 10,\ 1\leq a_i\leq 1000)$

输出格式

输出 $N$ 行。

第 $i$ 行输出一个整数，表示第 $i$ 位同学在满足“连续两轮不能分享同一种零食”的条件下，最多能够进行的分享轮数。

样例输入 #1

3
2 3 5
3 2 2 2
1 10

样例输出 #1

7
6
1

样例解释 #1

对于第 1 位同学，共有 3 包 A 和 5 包 B。

可以按如下顺序分享：

B A B A B A B

一共可以进行 7 轮。剩余的 1 包 B 无法继续加入，否则最后两轮都会是 B，因此答案为 7。

对于第 2 位同学，三种零食各有 2 包，可以按：

A B C A B C

分享全部 6 包零食，因此答案为 6。

对于第 3 位同学，只有一种零食。第一轮可以分享 1 包，但第二轮如果继续分享就一定与上一轮种类相同，因此答案为 1。

样例输入 #2

5
2 5 5
2 1 10
3 1 1 3
4 7 2 2 2
10 1 1 1 1 1 1 1 1 1 1000

样例输出 #2

10
3
5
13
19