题目描述

XC 的儿子小 XC 最喜欢玩的游戏是用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。

小 XC 是一个聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。因此他在垒城堡时总是遵循这个规则。

现在，小 XC 想把自己垒的城堡送给幼儿园的女孩子们。为了公平，他决定送给每个女孩子一样高的城堡。由于没有多余的积木，他需要通过从每个城堡中移去一些积木，使得所有城堡最终高度相同且尽可能高。

任务

编写一个程序，根据所有城堡的信息，决定应该移去哪些积木才能获得最佳效果。

输入格式

• 第一行是一个整数 n，表示城堡的数量。
• 接下来的 n 行，每行是一系列非负整数，用空格分隔，按从下往上的顺序给出每座城堡中所有积木的棱长，以 -1 结束。

输出格式

• 一个整数，表示最后城堡的最大可能的高度。
• 如果找不到合适的方案，则输出 0。

输入输出样例

输入样例1

2
2 1 -1
3 2 1 -1

输出样例1

3

数据范围

• 1 ≤ n ≤ 100
• 每座城堡的积木数目不超过 100
• 积木的棱长不超过 100