1018模拟赛周赛07

P3. 积木问题 (blocks)

描述

Tom 有 n 件积木，它们的长度不定，宽度是 1 或 2。现在他要把这些积木放入一个 2*m 的积木盒里（要求全部横放，不允许堆放、斜放），计算能容纳所有积木的最小 m 值。

输入

第一行是正整数 t(≤10)，表示数据组数；

每组数据中，

第一行为正整数 n(≤100)，表示积木数，接下来 n 行，每行两个正整数 a 和 b，分别表示每块积木的宽和长，其中 a=1 或 2，b≤100。

输出

对于每组数据，输出 m 的最小值。

样例

7
4

提示

样例 1 中，三块积木的摆放方式如下图所示：其中 1*2 的积木只能横放，不能斜放或堆放。

提交

题目参数

时间限制	1 秒
内存限制	128 MB