Хороший граф

Алекс так визначаж хороший граф:

• Одна вершина є хорошим графом.

• Якщо два хороших графа не мають спільних вершин, то і їх об'єднання також є хорошим графом.

• Якщо G – хороший граф, то

  

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

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

Вхідні дані

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

Наступні N рядків містять матрицю суміжності G.

Кожен з наступних N рядків містить ціле число w_i (1 ≤ w_i ≤ 1000) - вагу i-ої вершини.

Вихідні дані

У єдиному рядку вихідного файлу виведіть вагу максимальної кліки графа G.

Приклади