Select Sets

Time Limit : 5 sec, Memory Limit : 1048576 KB

Problem L: Select Sets

Problem

整数の集合がN個ある。 これらの集合にはそれぞれ1からNまでの番号が割り振られている。i番目の集合の要素数はKiであり、その集合の要素の中でj番目に小さい整数はai,jである。

太郎君はこの中から任意の数だけ集合を選ぶことになった。 ただ適当に選ぶだけではつまらないと思った太郎君は、少なくとも3つの集合を選ぶことにした。また、"選んだ集合の和集合の要素数"と"選んだ集合の積集合の要素数"の積ができるだけ大きくなるように選ぶことにした。

太郎君が最適に集合を選んだとき、"選んだ集合の和集合の要素数"と"選んだ集合の積集合の要素数"の積の最大値を求めよ。

Input

入力は以下の形式で与えられる。

N
K1 a1,1 a1,2 ... a1,K1
K2 a2,1 a2,2 ... a2,K2
...
KN aN,1 aN,2 ... aN,KN

Constraints

入力は以下の条件を満たす。

  • 入力は全て整数である。
  • 3 ≤ N ≤ 20,000
  • 1 ≤ ai,j ≤ 22
  • ai,j < ai,j+1 ( 1 ≤ iN ) ( 1 ≤ j < Ki)

Output

太郎君が最適に選んだときの"選んだ集合の和集合の要素数"と"選んだ集合の積集合の要素数"の積の最大値を出力せよ。

Sample Input 1

4
1 5
2 3 5
3 3 5 7
4 3 5 7 9

Sample Output 1

8

Sample Input 2

5
4 1 4 5 6
4 1 7 8 9
3 1 2 3
3 1 2 3
3 1 2 3

Sample Output 2

9

Sample Input 3

3
2 3 4
2 2 5
2 1 6

Sample Output 3

0

Source: Ritsumeikan University Programming Camp 2017 , Day 2, Shiga, Japan, 2017-03-23