Problems

# Good Graphs

# 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**.

Input example #1

4 0000 0011 0101 0110 100 1 2 3

Output example #1

100