题目描述

有 $N$ 名选手（$N$ 为偶数且不小于 $4$），任意两名选手之间有一个配合度，表示他们组队时的默契程度。比赛开始前，所有选手都是自由的。

比赛分为两个阶段：

选人阶段：小涵和计算机轮流从自由选手中选择一名加入自己的队伍（小涵先选），直到所有选手被均分完毕。

对抗阶段：程序自动从双方队伍中各挑出一对配合度最高的选手组合进行对抗，配合度更高的一方获胜。

计算机的策略是：每轮选择时，它会尝试将小涵队伍中的每名选手与每名自由选手配对，找出配合度最高的组合，并将该组合中的自由选手选入自己的队伍（破坏小涵的最强组合）。

已知所有选手组合的配合度均不相同。小涵想知道，如果计算机始终坚持上述策略，自己能否获胜？如果能，在所有获胜情况中，自己最终选出的选手组合的最大配合度是多少？

输入格式

共 $N$ 行。

第一行为一个偶数 $N$，表示选手的个数。

第 $2$ 行到第 $N$ 行里，第 $i+1$ 行有 $N-i$ 个非负整数，每两个数之间用一个空格隔开，表示 $i$ 号选手和 $i+1,i+2,\dots,N$ 号选手之间的配合度（$0 \le \text{配合度} \le 10^9$）。

输出格式

共一或二行。

若存在可以让小涵获胜的选择顺序，则输出 $1$，并另起一行输出所有获胜情况中，小涵最终选出的选手组合的最大配合度。如果不存在可以让小涵获胜的选择顺序，则输出 $0$。

样例

6
5 28 16 29 27
23 3 20 1
8 32 26
33 11
12

1
32

提示

对于 $40\%$ 的数据有 $N \le 10$。

对于 $70\%$ 的数据有 $N \le 18$。

对于 $100\%$ 的数据有 $4 \le N \le 500$。保证所有选手组合的配合度均不相同。