语言学家

题目

每天不好好背单词就会利滚利滚利滚利滚利……

小J和小R最近迷恋上了研究新的语言，他们在研究一种「绿鸟语」，它由 K 种鸟语字母构成，小J和小R直接以数字 1 到 K 表示。

「绿鸟语」中每个字符串都有对应的价值。所有长度为 2 的字符串的价值是被规定的。一个字符串的价值为它所有长度为 2 的子串（这里要求两个字符相邻才认为是子串，中间不能有任何其他字符）的价值和。

现在小J和小R知道了这 K 个字母两两相连能够得到的所有价值。

请你求出通过构造能得到的价值最大的字符串的价值。如果不存在这样的字符串，输出 −1。

输入：本题输入文件包含多组数据。第一行一个正整数 T 表示数据组数；对于每组数据：第一行一个整数 K；接下来 K 行，每行 K 个整数，第 i 行的第 j 个整数表示第 i 个字符和第 j 个字符拼接成的字符串的价值 w_i,j。
输出：对于每组数据输出一行一个整数表示答案。

样例：

2
5
0 -2 2 -27 -7
2 0 4 -19 -3
-8 -12 0 -19 -9
7 4 3 0 3
1 1 9 -18 0
2
0 2
-1 0

12
-1

提示：对于 20% 的数据，保证 1≤K≤10。对于 60% 的数据，保证 1≤K≤50。对于 100% 的数据，保证 1≤T≤5，1≤K≤100，−10⁶≤w_i,j≤10⁶。

思路

复杂度分析

• 时间复杂度：
• 空间复杂度：

← 返回菜鸟的coding