Problems
Good Graphs
Good Graphs
Alex defined \textit{good graphs}:
\begin{itemize}
\item Single vertex is a \textit{good graph}.
\item If two \textit{good graph} have no common vertex then their union is a \textit{good graph}.
\item If \textbf{G} is a \textit{good graph} then
\includegraphics{https://static.e-olymp.com/content/07/077236f94e5669773b845004c0266c9b4791bd42.jpg}
(complement of \textbf{G}) is a \textit{good graph}.
\end{itemize}
Try to solve the problem of finding maximal weighted clique in a \textit{good graph}.
\InputFile
The first line of contains the integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{500}) - number of vertices in the \textit{good graph} \textbf{G}.
The next \textbf{N} lines contain adjacency matrix of \textbf{G}.
Each of last \textbf{N} lines contains the integer \textbf{w_i} (\textbf{1} ≤ \textbf{w_i} ≤ \textbf{1000}) - the weight of \textbf{i}^th vertex.
\OutputFile
In the single line of the output file print the maximal weight of clique of graph \textbf{G}.
Input example #1
4 0000 0011 0101 0110 100 1 2 3
Output example #1
100