Good Graphs#3417

Good Graphs

1 second

64 megabytes

Medium

Alex defined good graphs:

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

Input

The first line contains the integer $N$ ( $1 \leq N \leq 500$ 1 \leq N \leq 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}$ w_i ( $1 \leq w_{i} \leq 1000$ 1 \leq w_i \leq 1000) - the weight of $i$ -th vertex.

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

Example 1

Loading

1 \leq N \leq 500

w_{i}

1 \leq w_{i} \leq 1000