Матрица

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

Технические условия

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

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

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

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 256 MB
Баллы за пройденный тест: 5
Сложность: 100% 0/6

Пример

Пример входных данных

2
1 1
1 1

Пример выходных данных

2
1 1
2 2

← И снова сумма...

Список задач