Хороший граф

Алекс так определяет хороший граф:

• Одна вершина является хорошим графом.

• Если два хороших графа не имеют общих вершин, то и их объединение также является хорошим графом.

• Если G – хороший граф, то

  

  (дополнение к G) также является хорошим графом.

Попробуйте решить задачу нахождения в хорошем графе клики с максимальным весом.

Входные данные

Первая строка входного файла содержит одно целое число N (1 ≤ N ≤ 500) - число вершин в заданном хорошем графе G.

Последующие N строк содержат матрицу смежности G.

Каждая из последующих N строк содержит целое число w_i (1 ≤ w_i ≤ 1000) - вес i-ой вершины.

Выходные данные

В единственной строке выходного файла выведите вес максимальной клики графа G.

Примеры