题目描述

为了在全市打响宣传阵地仗，旺仔牛奶的生产商决定在全市中小学邀请一群有影响力的“学习之星”来为它们做代言，利用学生和家长（尤其是后者）对成绩的执着追求，来打造“喝旺仔牛奶的都是dalao”的品牌印象。李子明同学发现这是一个当（hui）选大队长的好机会，于是他抽了一整个周末的时间去准备代言人的面试。
李子明得知和他一同参加面试的有\(N\)人，这\(N\)人在指定的时间逐个接受面试官的考核。根据自己长期阅人的经验，他认为被面试的次序会影响考官的评分。如果排在前边的某个人非常能说会道，一张抹了蜜的小嘴能让考官当场神魂颠倒，那么这个人有可能就成了考官的既定人选，之后那些不善于取悦人的被面试者就会处于更大的劣势；但如果面试次序翻转一下，考官就会更加留意其他人的优势。
对所有被面试者和考官做了一个简单评估后，李子明总结出了一个数学模型：将\(N\)名被面试者编号为\(1 \sim N\)，李子明自己是1号，每个人固有的“能力值”为\(A_i\)，被面试的顺序可以看成\(1 \sim N\)的一个全排列。如果编号为\(i\)的人比编号为\(j\)的人先被面试，那么编号为\(j\)的人就会额外获得一个“比较印象分”\(S_i \times c_{i,j}\)（有可能是负数），其中\(S_i\)为编号为\(i\)的人的面试成绩，\(c_{i,j}\)为某个常数。编号为\(k\)的人最终的面试成绩可以估计为\(S_k = A_k + \sum S_i \times c_{i,k}\)，即自身的能力值，加上在他之前所有被面试者给他造成的比较印象分。
李子明想让自己的面试成绩尽可能高，所以他想要在面试开始之前，说服考官和其他被面试者按照他指定的顺序进行面试。请你输出他的面试成绩最大可以是多少。

输入格式

输入第一行是一个正整数\(T\)，表示数据的组数。之后每组数据：
第一行是一个正整数\(N\)；
第二行是\(N\)个 浮点数 \(A_1, A_2 \cdots A_N\)；
之后\(N\)行，每行\(N\)个 浮点数 ，该部分第\(i\)行第\(j\)列的数为\(c_{i,j}\)。规定\(c_{i,i} = 0\)
输入的所有浮点数至多保留3位小数。

输出格式

每组数据输出一行，分别输出李子明的最大面试成绩四舍五入保留3位小数的结果。（提示：用printf("%.3f", value)输出浮点数，数据保证double类型的浮点数运算误差不会影响输出）

样例

输入

2  
3
10 50 25
0 -0.1 -0.15
0.05 0 -0.03
0.06 -0.02 0
5
300 500 450 250 300
0 -0.01 0.04 -0.06 0
0.03 0 0.02 -0.05 -0.07
0.03 0.09 0 -0.02 0.04
0 0.01 -0.1 0 -0.03
-0.06 0.02 0.06 0 0

输出

13.975
329.787

样例说明

在第1组样例中，达成最优解的面试顺序是3→2→1。
\(S_3 = A_3 = 25\)
\(S_2 = A_2 + S_3 C_{3, 2} = 50 + 25 \times (-0.02) = 49.5\)
\(S_1 = A_1 + S_3 C_{3, 1} + S_2 C_{2, 1} = 10 + 25 \times 0.06 + 49.5 \times 0.05 = 13.975\)

数据规模及约定

\(T \le 10, \quad N \le 8, \quad 0.0 < A_i < 1000.0, \quad -1.0 < c_i < 1.0\)