問題文

$1,2,\dots,N$ の番号が付いた $N$ 個の袋と中に何も入っていない $1$ 個の箱があります。
袋 $i$ $(1 \leq i \leq N)$ には $T_{i}$ 個の石が入っており、このうち $j$ $(1 \leq j \leq T_{i})$ 番目の石の質量は $A_{i,j}$ です。

コアさんは、これらの袋と石と箱を用いて、$i=1,2,\dots,N$ の順に次の操作を行います。

1. まず、石が $1$ 個以上入っている袋を自由に $1$ 個選び、その中の石をすべて箱の中に入れる。

2. 次に、箱の中にある石の個数を $n$ として、これら $n$ 個の石のうち、次の条件を満たすものの中から無作為に $1$ 個選ぶ。
   ここで、$x = \min(K_{i}, n)$ とする。

   • $n$ 個の石の質量が降順に $a_{1}, a_{2}, \dots, a_{n}$ $(a_{1} \geq a_{2} \geq \cdots \geq a_{n})$ と表されるとき、自身の質量が $a_{x}$ に等しい。

3. 最後に、選んだ石以外の $n-1$ 個の石をすべて箱の中から取り出して食べる。

すべての $i$ に対して操作を終了した後、箱の中に残るただ $1$ 個の石の質量としてあり得るものの最大値を求めてください。

制約

• $1 \leq N \leq 10^{5}$

• $1 \leq T_{i} \leq 10^{5}$ $(1 \leq i \leq N)$

• $T_{1}, T_{2}, \dots, T_{N}$ の総和は $10^{5}$ 以下

• $1 \leq A_{i,j} \leq 10^{9}$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq T_{i})$

• $1 \leq K_{i} \leq 3 \times 10^{5}$ $(1 \leq i \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$K_{1}$ $K_{2}$ $\cdots$ $K_{N}$
$T_{1}$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,T_{1}}$
$T_{2}$
$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,T_{2}}$
  $\vdots$
$T_{N}$
$A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,T_{N}}$

• $1$ 行目には $N$ が与えられる

• $2$ 行目には $K_{1}, K_{2}, \dots, K_{N}$ がこの順に半角スペース区切りで与えられる

• $2 i + 1$ $(1 \leq i \leq N)$ 行目には $T_{i}$ が与えられる

• $2 i + 2$ $(1 \leq i \leq N)$ 行目には $A_{i,1}, A_{i,2}, \dots, A_{i,T_{i}}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

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

9

5
2 2 2 1 2
1
1
1
10
1
100
1
1000
1
10000

1000

9
4 2 10 7 3 300000 7 1 5
5
7 1433 233 441445814 14
8
84906649 75121583 12 603415 10147 199004 65221 151278232
7
129002 468 235 250 1144 38994 1070804
10
122230317 19048460 168635 817 24296790 17 6404 49328 194386 61986
5
18 11 408 1 2
1
7
10
339112 57 159599 209673 234036624 277265898 34115930 17787 13825 20151
9
16 2337 557 185983 823 47160 712213 20538 100
3
829 10 9307

603415