T102847 字符串问题

喵星球的语⾔与⼈类不同，由$k$种字母构成，我们这⾥直接以数字 $1 \sim k$ 表⽰。 喵星球上每个字符串都有对应的价值。所有长度为2的字符串的价值是被规定的。⼀个字符串的价值为它所有长度为2的⼦串的价值和。 请你求出价值最⼤的字符串的价值。如果不存在这样的字符串，输出`-1`。

本题输⼊⽂件包含多组数据。 第⼀⾏⼀个正整数$T$表⽰数据组数。 对于每组数据： 第⼀⾏⼀个整数 $k$。 接下来$k$ ⾏，每⾏$k$ 个整数，第$i$ ⾏的第$j$ 个整数表⽰第$i$ 个字符和第$j$ 个字符拼接成的字符串的价值 $w_{i,j}$。

对于每组数据输出⼀⾏⼀个整数表⽰答案。

对于$20\%$的数据，$1 \le k \le 10$ 。 对于$60\%$的数据，$1 \le k \le 50$ 。 对于$100\%$的数据，$1 \le T \le 5,1 \le k \le 100,-10^6 \le w_{i,j} \le 10^6$ 。