文理学院程序设计在线练习


猴子取桃

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 24   Accepted Submission(s): 13
Problem Description

花果山上有n个景点(假设编号为1~n),每个景点存放着一定数量的桃子。
部分景点之间有道路直接相通,但是景点之间的道路有一个特点:道路的方向是单向的且一定是从小的编号通向大的编号。

现在的任务是:
任选一个开始的起点,并且沿着可达的道路走到另一个景点,只要有道路通向未走过的景点就可以重复这个过程,一直到无路可走为止。

在行进过程中,可以收集所经过的景点的桃子。现在请你来算一下,看看最多可以收集到多少数量的桃子?

Input

输入数据的第一行为一个正整数T(0<T<=20),表示测试数据的组数,然后是T组测试数据。
每组测试的第一行是整数n(0 < n <= 100),表示景点总数。
每组测试的第二行是n个整数,分别表示存放在每个景点i的桃子数Ai(0<Ai<10000,1<=i<=n)。
再接下来有n行数据,每行n个数,均由0或1构成,代表n个景点的连通状况,其中1代表连通,0代表不通。
也就是说,若第i行第j列的数Mij是1,则表示景点i和景点j之间存在通路,否则表示景点i和景点j之间没有通路。
注意:由于不存在从编号大的景点通向编号小的景点的道路,所以,当i>=j时,Mij一定是0。

Output

对于每组测试,输出最多可以收集到的桃子数。

Sample Input
3
3
10 20 5
0 0 1
0 0 0
0 0 0
3
5 10 5
0 1 1
0 0 0
0 0 0
6
5 10 20 5 4 5
0 1 0 1 0 0
0 0 0 1 0 0 
0 0 0 1 0 0
0 0 0 0 1 1 
0 0 0 0 0 1
0 0 0 0 0 0 
Sample Output
20
15
34
Source

2012校计算机技能竞赛