在网络中，两台计算机需要发送数据包来进行相互间的通信。如果一台计算机无法直接和目标计算机连通，它会把数据包发送到已连通的所有计算机，这些计算机收到后会立即将数据包转发给各自所有直接连通的计算机，直到到达目标计算机完成通信。

现在有 n 台计算机，编号从 1 到 n ，其中第 i台、第 j 台计算机间相互发送数据包需要时间为 A[i][j]。现在 1 号计算机请求与所有计算机通信，并向网络中发送了数据包。问经过多少时间后所有的计算机都会收到这个数据包。

输入的网络保证所有的计算机之间最终是可以相互通信的。

第一行输入一个整数 n。

之后第 2~n 行，第 i 行输入 i-1 个数。其中第 j 个数表示第 i 、j 台计算机之间直接通信时发送数据包需要 A[i][j] 的时间。若第  i，j 台计算机未直接相连通则输入一个字符 x。

输出一个整数表示答案。

100\%的数据：1\leq n,A[i][j] \leq 100