Мережевий диверсант#2647
Університетська мережа складається з комп'ютерів. Системні адміністратори зібрали інформацію про трафік між вузлами та розділили мережу на дві підмережі, щоб мінімізувати трафік між ними.
Після відрахування незадоволений студент-комп’ютерник на ім’я Вася вирішив помститися. Він зламав університетську мережу та спробував перевизначити комп’ютери так, щоб максимізувати трафік між двома підмережами.
На жаль, він зрозумів, що знайти таке найгірше розбиття — це одна з тих задач, які він не міг розв’язати під час навчання. Тому він звертається до вас, більш успішного студента-комп’ютерника, по допомогу.
Дані про трафік надані у вигляді матриці , де C_{ij} — обсяг даних, які передаються між -м та -м вузлами (C_{ij} = C_{ji}, C_{ii} = 0). Мета — розбити вузли мережі на дві неперетинні підмножини і так, щоб сума трафіку між ними була максимальною.
У першому рядку вхідного файлу задано кількість вузлів (2 \leq N \leq 20). Далі йдуть рядків по цілих чисел у кожному — матриця трафіку (0 \leq C_{ij} \leq 10000).
Вихідний файл повинен містити одне ціле число — максимальний трафік між підмережами.
Приклад 1