Матрица

Вам дана матрица целых чисел размера n×n. Ваша задача - найти такой набор координат (k_i, l_i), в котором каждая координата k_i и каждая координата l_i встречается ровно один раз, такой, чтобы минимизировать сумму выбранных элементов.

Входные данные

Первая строка входного файла содержит одно целое число n (1 ≤ n ≤ 239). Следующие n строк содержат по n целых чисел в каждой. Все эти числа не превосходят по абсолютной величине 10^6.

Выходные данные

Первая строка должна содержать значение оптимизируемой функции. В следующие n строк необходимо записать пары чисел, описывающих выбранные ячейки. Первой координатой выводится номер строки.

Примеры