1018模拟赛周赛07
P3. 积木问题 (blocks)
Description
Tom 有 n 件积木，它们的长度不定，宽度是 1 或 2。现在他要把这些积木放入一个 2*m 的积木盒里（要求全部横放，不允许堆放、斜放），计算能容纳所有积木的最小 m 值。
Input
第一行是正整数 t(≤10)，表示数据组数；
每组数据中，
第一行为正整数 n(≤100)，表示积木数，接下来 n 行，每行两个正整数 a 和 b，分别表示每块积木的宽和长，其中 a=1 或 2，b≤100。
Output
对于每组数据，输出 m 的最小值。
Examples
Input
2 3 1 2 2 2 2 3 3 1 2 1 2 1 3
Output
7 4
Hint
样例 1 中，三块积木的摆放方式如下图所示：其中 1*2 的积木只能横放，不能斜放或堆放。
Submit
题目参数
| Time Limit | 1 second |
| Memory Limit | 128 MB |