Sticks

Time limit1sMemory limit128 MB

Summary

From sticks grouped by colour, find three sticks of pairwise different colours that form a non-degenerate triangle and maximise the perimeter.

Level: Medium7 of 10
Topics: Sorting, Greedy, Two pointers
Solved: No attempts yet

Problem

Little Johnny received a birthday present from his grandparents: a box of sticks of various lengths and colours. Johnny wonders whether he can pick three sticks that form a triangle whose three sides all have different colours. He only cares about non-degenerate triangles, that is, triangles with positive area.

Among all triangles that can be built from three sticks of three pairwise-different colours, find the one with the largest perimeter and report that perimeter.

Input

The first line contains an integer $k$ ( $3 \le k \le 50$ ), the number of different stick colours. The colours are numbered from $1$ to $k$ .

Each of the next $k$ lines describes the sticks of one colour. Line $i+1$ describes the sticks of colour $i$ : it begins with an integer $n_i$ ( $1 \le n_i \le 1{,}000{,}000$ ), the number of sticks of that colour, followed on the same line by $n_i$ integers separated by single spaces, the lengths of those sticks. Every length is a positive integer not exceeding $1{,}000{,}000{,}000$ . The total number of sticks does not exceed $1{,}000{,}000$ .

Output

Print a single line.

If at least one triangle with three pairwise-different-coloured sides and positive area can be formed, print the maximum possible perimeter of such a triangle (the sum of its three side lengths).

Otherwise, print -1.

A triangle with sides $a \le b \le c$ has positive area (is non-degenerate) exactly when $a + b > c$ .

Examples3

Example 1
Input
```
4
1 42
2 6 9
3 8 4 8
1 12
```
Expected output
```
29
```
Example 2
Input
```
3
1 1
1 2
1 100
```
Expected output
```
-1
```
Example 3
Input
```
3
1 5
1 5
1 5
```
Expected output
```
15
```