题目描述

世一大的小粉兔ddl非常多。

小粉兔有$n$个ddl，按照过期时间从小到大排列。赶完第$i$个ddl可以让粉兔获得$V_i$冒险阅历。

由于粉兔有强迫症，在剩下的ddl中，粉兔每次只能赶过期时间最小的或者第三小的ddl。 由于粉兔的脑容量太小，对于任意$i,j$，粉兔也许不能在赶完第$i$个ddl后赶第$j$个ddl。第一次赶的ddl没有限制。

实际上时间对粉兔来说根本不是问题，但是粉兔脑容量有限，可能赶不完所有ddl。粉兔还要回去玩原神，所以想知道如何使自己获得的冒险阅历之和最大化。

输入格式

第一行包含一个整数 $n$，表示ddl的个数。

第二行是$n$个整数$V_1,V_2,\cdots,V_n$。

接下来$n$行，每行一个长为$n$的字符串$s_i$。字符集为$0,1$。

粉兔可以在赶完ddl $i$后赶ddl $j$当且仅当$s_{i,j}=1$。

输出格式

输出一个整数表示最大冒险阅历。

样例

Input

6
1 2 4 8 16 32
000110
000001
000101
010000
110000
000000

Output

43

Hint

依次赶编号为1，4，2，6的ddl。赶到ddl的时候它们的排名依次是1，3，1，3。

数据范围

对于所有数据，$n\le 1919, 1\le V_i\le 10^6$。

子任务1(10分). $n\leq 9$。

子任务2(10分). $n\leq 20$。

子任务3(20分). $n\leq 88$。

子任务4(20分). $n\leq 488$。

子任务5(40分). 无特殊限制。