아기 엘크

얼마 전 플랫랜드 대자연보호구역 경계에 마법의 숲이 나타났고, 호기심 많은 아기 엘크 한 마리가 그곳에 가 보기로 했다. 마법에 걸린 나무들 사이를 몇 시간 헤맨 끝에 아기 엘크는 숲을 빠져나왔다. 그 뒤로 아기 엘크는 훨씬 덜 호기심 많아졌다. 그런데 집에 돌아와 보니 뿔의 폭이 눈에 띄게 넓어져 있었다. 뿔이 클수록 엘크 무리에서 영향력이 커지기 때문에, 다른 엘크들은 마법의 숲에 대한 자세한 지도를 요구했다.

아기 엘크는 자기에게 일어난 일을 놀라울 만큼 잘 기억하고 있었다. 아기 엘크의 말에 따르면 숲은 $N$개의 평행한 줄로 나뉘어 있고, $i$번째 줄에는 $k_i$그루의 나무가 있다. 각 줄에서 이웃한 나무 사이의 거리는 정확히 기억하고 있었다. 마법의 숲에서 거리가 $d$인 두 나무 사이를 지나면 뿔이 $d$까지 자란다.

엘크들은 숲에서 앞으로만 이동할 수 있다고 합의했다. $i$번째 줄에서 $i+1$번째 줄로만 이동한다. 두 나무 사이의 거리가 뿔의 폭보다 크면 그 사이를 지날 수 없다. 숲에 들어가기 전 뿔의 폭은 $0$이었다고 할 때, 숲을 나올 때 엘크 뿔의 폭이 가질 수 있는 최댓값을 구하라.

첫 줄에 나무 줄의 개수 $N$이 주어진다. $2 \le N \le 10^3$이다. 다음 $N$개의 줄에는 각 줄의 정보가 주어진다. $i$번째 줄의 첫 번째 수는 그 줄에 있는 나무의 개수 $k_i$이며, $2 \le k_i \le 10^3$이다. 그 뒤에 $k_i - 1$개의 양의 정수가 주어지는데, 이는 $i$번째 줄에서 이웃한 나무 사이의 거리이고 각 값은 $10000$을 넘지 않는다.

숲을 빠져나올 수 있다면 뿔 길이의 최댓값을 한 개의 수로 출력한다. 빠져나올 수 없다면 $-1$을 출력한다.