Поламаний свіч#6360
Накривши стіл і ведучи приємну бесіду, наші герої розповіли містеру Нетворку про свою подорож світом. "Я бачу ви полюбляєте вирішувати цікаві задачі?" – сказав містер Нетворк – "Тоді тримайте ще одну з моєї виробничої практики".
"Якось я займався налаштуванням комп'ютерної мережі у фірмі де тоді працював. Фірма мала комп'ютерів. Свіч, до якого були підключені усі комп'ютери, почав сильно збоїти, і тому не будь-які два комп'ютери могли зв'язатися один з одним. Крім того, якщо комп'ютер обмінювався інформацією з комп'ютером , то ніякі інші комп'ютери не могли у цей час обмінюватися інформацією ні з , ні з . Вам необхідно обчислити максимальну кількість комп'ютерів, які могли одночасно брати участь у процесі обміну інформацією" – закінчив свою розповідь містер Нетворк.
У першому рядку файлу задано ціле число (1 \le N \le 18). Далі йдуть рядків по символів, причому -ий символ -го рядка дорівнює '', якщо -ий і -ий комп'ютери можуть обмінюватися інформацією, інакше він дорівнює ''. -ий символ -го рядка завжди дорівнює '', крім того, матриця символів симетрична.
Виведіть максимальну кількість комп'ютерів, які можуть одночасно брати участь у процесі обміну інформацією.
Приклад 1