兰尼斯特王国有 n 座城堡,有城墙连接两座城堡,没有两座城堡由多于一堵墙连接,没有城墙将城堡与其自身连接。
詹姆·兰尼斯特爵士发现丹妮莉丝·坦格利安即将攻击他的王国。因此他要保卫自己的王国。他有 k 升一种奇怪的液体。他想在城堡之间分配该液体,因此每个城堡可能包含一些液体(可能为零或非整数升)。之后墙的稳定性定义如下:如果墙连接两个城堡a和b,并且它们分别含有x和y升该液体,则该墙的强度为x·y。
你的任务是打印詹姆·兰尼斯特爵士可以达到的最大可能的墙壁稳定性总和。
输入
输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 40, 1 ≤ k ≤ 1000)。
接下来是 n 行。这些行的第 i 行包含 n 个整数 ai, 1, ai, 2, ..., ai, n ($$a_{i,j} \in \{0,1\}$$)。如果城堡 i 和 j 有墙连接,则 ai, j = 1。否则等于 0。
对于所有 1 ≤ i、j ≤ n,保证 ai, j = aj, i 且 ai, i = 0。
输出
打印詹姆·兰尼斯特爵士能够达到的最大可能的城墙稳定性总和。
如果您的答案的绝对或相对误差不超过 10 - 6,则视为正确。
即:假设你的答案是a,陪审团的答案是b。如果 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$,检查程序将认为您的答案正确。
示例
输入 #1
3 1 0 1 0 1 0 0 0 0 0
输出 #1
0.250000000000
输入 #2
4 4 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
输出 #2
4.000000000000
注意
在第一个样本中,我们可以分别为城堡 1、2、3 分配 0.5、0.5、0 升液体,以获得最大总和 (0.25)。
在第二个示例中,我们可以分别为城堡 1、2、3、4 分配 1.0、1.0、1.0、1.0 升液体,以获得最大总和 (4.0)