Мережевий диверсант
Мережа університету складається з N комп'ютерів. Системні адміністратори зібрали дані про трафік між вузлами та ретельно розділили мережу на дві підмережі, щоб мінімізувати трафік між ними.
Однак студент факультету комп'ютерних наук Вася, після виключення з університету, вирішив помститися. Він зламав університетську мережу і вирішив перепризначити комп'ютери, щоб максимізувати трафік між двома підмережами.
На жаль, він зрозумів, що обчислення такого найгіршого поділу є однією з тих задач, які він, будучи студентом, не зміг вирішити. Тому він звертається до вас, більш успішного студента комп'ютерних наук, за допомогою.
Дані про трафік представлені у вигляді матриці C, де C_ij — це кількість даних, що передаються між i-м та j-м вузлами (C_{ij }= C_ji, C_{ii }= 0). Завдання полягає в тому, щоб розділити вузли мережі на дві неперетинні підмножини A і B так, щоб максимізувати суму трафіку між ними.
Вхідні дані
Перша строка вхідного файлу містить кількість вузлів N (2 ≤ N ≤ 20). Наступні N рядків, що містять N цілих чисел, розділених пробілами, представляють матрицю трафіку C (0 ≤ C_ij ≤ 10000).
Вихідні дані
Вихідний файл повинен містити одне ціле число — максимальний трафік між підмережами.