Сетевой диверсант
Университетская сеть состоит из 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).
Выходные данные
Выходной файл должен содержать одно целое число — максимальный трафик между подсетями.