You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

4# 题目背景

小 H 是一位热爱音乐的学生。

题目描述

小 H 准备听 $n$ 首歌，每两首歌之间都有一定的相似程度（相似程度是一个范围 $[0,1]$ 的小数，自己和自己的相似程度为 $1$，同样的两首歌的相似程度是固定的），请你帮他安排一个最佳顺序（每首歌至多只能播放一次），使得所有相邻的两首歌之间的相似程度和最大，求出这个最大的和。

格式

输入

第一行一个整数 $n$，接下来 $n \times n$ 个小数，表示每首歌之间的相似程度。

输出

一个小数表示答案，四舍五入保留 $3$ 位小数。

样例

3
1.0 0.5 0.3
0.5 1.0 0.6
0.3 0.6 1.0

1.100

解释

按照 $1$ -> $2$ -> $3$ 的顺序听这三首歌，相似程度和为 $0.5+0.6=1.1$，可以证明这是最大的和。

限制

对于所有数据，保证 $2 \leq n \leq 17$，

对于 $10\%$ 的数据，保证所有歌曲两两之间的相似程度都为 $1$，

另有 $40\%$ 的数据，保证 $n \leq 9$.