Good Graphs

Alex defined good graphs:

• Single vertex is a good graph.

• If two good graph have no common vertex then their union is a good graph.

• If G is a good graph then

  

  (complement of G) is a good graph.

Try to solve the problem of finding maximal weighted clique in a good graph.

Input

The first line of contains the integer N (1 ≤ N ≤ 500) - number of vertices in the good graph G.

The next N lines contain adjacency matrix of G.

Each of last N lines contains the integer w_i (1 ≤ w_i ≤ 1000) - the weight of i^th vertex.

Output

In the single line of the output file print the maximal weight of clique of graph G.

Examples