막대기

어린 재훈이는 조부모님께 생일 선물로 여러 길이와 색의 막대기가 담긴 상자를 받았다. 재훈이는 이 막대기들 중에서 세 변의 색이 모두 다른 삼각형을 만들 수 있는 막대기 세 개가 있는지 궁금하다. 단, 재훈이가 관심 있는 것은 넓이가 양수인, 즉 찌그러지지 않은(비퇴화) 삼각형뿐이다.

색이 서로 다른 세 막대기로 만들 수 있는 삼각형 중에서, 둘레가 가장 긴 삼각형의 둘레를 구하여라.

첫째 줄에 막대기 색의 개수를 나타내는 정수 $k$ ($3 \le k \le 50$)가 주어진다. 색은 $1$번부터 $k$번까지 번호가 매겨져 있다.

이어지는 $k$개의 줄에는 각 색의 막대기 정보가 주어진다. $i+1$번째 줄은 색 $i$의 막대기를 설명하며, 먼저 그 색의 막대기 개수 $n_i$ ($1 \le n_i \le 1{,}000{,}000$)가 주어지고, 이어서 같은 줄에 $n_i$개의 정수가 공백으로 구분되어 주어지는데 이는 각 막대기의 길이이다. 모든 길이는 $1{,}000{,}000{,}000$ 이하의 양의 정수이다. 전체 막대기의 개수는 $1{,}000{,}000$개를 넘지 않는다.

한 줄에 답을 출력한다.

세 변의 색이 모두 다르고 넓이가 양수인 삼각형을 하나라도 만들 수 있다면, 그러한 삼각형의 둘레(세 변 길이의 합)의 최댓값을 출력한다.

만들 수 없다면 -1을 출력한다.

세 변의 길이가 $a \le b \le c$인 삼각형은 $a + b > c$일 때에만 넓이가 양수(비퇴화)이다.