生日Party

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Sherlock的生日即将来临,Sherlock打算邀请几个好友来参加自己的生日Party。为了让Party尽可能的happy,经过Sherlock的调查发现每个好友都有一个happy值。而且Sherlock的好友之间也存在复杂的关系,当好友中的某两个人同时出现在Party的时候,会产生一个额外的happy值,幸亏Sherlock好友不算多,Sherlock打算邀请部分或全部好友(也可能一个都不邀请),好让Party的happy值最高

Input

有多组数据,首先一个整数T表示所给数据的组数。每组数据第一行一个整数n(0<n<=15),表示Sherlock的好友人数。第二行n个整数依次表示每个好友如果来参加Party将会产生的happy值,接下来n行,每行n个整数,第i行的第j个整数表示当第i个好友和第j个好友同时参加party是产生的额外happy值
注意,所给数据中的happy值的范围为(-100~100)

Output

每组数据输出一行,Sherlock的Party最高的happy值

Sample Input

4
2
1 2
0 -2
-2 0
3
-1 -1 0
0 1 1
1 0 1
1 1 0
3
1 1 1
0 -1 -1
-1 0 -1
-1 -1 0
3
-1 -1 -1
0 -2 -2
-2 0 -2
-2 -2 0

Sample Output

2
1
1
0

Hint

 

Source