In Kingdom of Byteland,there are N jewellery shops that connected by road such that there is zero or more bidirectional way to go from one shop to another.
Each shops has Jewellery of certain type.

Jewellery in Byteland has special property : if 'x' type jewellery is combined with 'y' type jewellery then it gets converted to (x xor y) type jewellery.

Cost of jewellery of type 'n' : n (in decimal representation)
Don SRK decided to rob the Kingdom of jewellery shops.He starts to rob from any shop and Rob as many shops as possible such that it maximizes the cost of jewellery he possesses.

Input:

The first line of input consists an integer n (1 ≤ n ≤ 100)followed by n x n matrix A

if A[i][j] = 'Y' then there is road from i to j , otherwise 'N' no road between them.

Next Line contains n integers => type[i] : representing type of jewellery in ith shop .(0 ≤ type[i] ≤ 1023)

Output:

Print an integer indicating Maximum cost of jewellery Robbed by Don.

SAMPLE INPUT
5
NYYYY
YNNNN
YNNNN
YNNNN
YNNNN
0 4 8 32 512

SAMPLE OUTPUT
556

见题面

见题面