题目描述

有偶数名队员，两人一组时会产生一个互不相同的默契值。小婷与小泽轮流从尚未被选走的队员中各选一人，小婷先选；最后小婷所选队员中默契值最大的两人成为她的组合，小泽同理。双方都采用最优策略。判断小婷能否使自己的组合默契值严格大于小泽，并在能获胜时输出她能保证的最大默契值。

输入格式

第一行偶数 $N$。随后第 $i$ 行（$1\le i<N$）给出 $N-i$ 个整数，依次是队员 $i$ 与 $i+1,\ldots,N$ 的默契值。

输出格式

若小婷不能保证获胜，输出一行 $0$；否则第一行输出 $1$，第二行输出她能保证的最大默契值。

输入

6
6 13 14 2 9
5 11 15 1
7 3 4
8 10
12

输出

1
13

输入

8
23 25 4 7 11 20 8
2 10 18 15 21 9
12 27 22 26 14
13 19 16 28
5 17 6
24 1
3

输出

1
26

输入

8
4 23 6 10 17 15 16
5 26 19 13 24 11
12 18 25 21 7
28 20 9 22
8 3 1
14 2
27

输出

1
26

数据范围

$4\le N\le500$；默契值在 $[0,10^9]$，所有两人组合的值互不相同。