Goodfellas

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Ta’zieh is a special kind of traditional Persian performing arts. It dates before the Islamic era and the tragedy of Siawush is one of the best examples.

Ta’zieh is usually performed on a round stage. Long ago when Ta’zieh was more popular, people of different families was gathering around the stage to watch the show. Each family had some male members and some female members. People could stand around the stage in any order although they should comply with these restrictions:

• A man and a woman from different families cannot stand beside each other.
• People can stand in several circular rows. But in each row they should stand tight, so everybody is considered to be adjacent to the persons (if any) who are standing next and previous to him.

You are studying the behavior of ancient people to learn more about their social attitude, traditions etc. Given description of some families in a Ta’zieh show, you have to find the minimum number of rows they could form while all restrictions are  satisfied.

Input

Input contains several test cases. Number of tests is at most 100. The first line of each test contains a single integer n (1 ≤ n ≤ 100), the number of families.

Next line will contain n integer’s m_i, the number of men in the i-th family. Description of women in each family w_i will follow in the same format (0 ≤ w_i, m_i ≤ 9). It is guaranteed that for any i between 1 and n, w_i+m_i > 0.  Input terminates with n = 0.

Output

For each test you should output the minimum number of circular rows that are required, so that each people can watch the show without violating the rules.

Sample Input

2
1 1
0 1
3
2 1 3
0 9 2
0

Sample Output

2
1

Submit

Source: 4th Kashan University's ACM Contest