eolymp
bolt
Try our new interface for solving problems
Problems

Матрица (Easy)

Матрица (Easy)

Time limit 1 second
Memory limit 64 MiB

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

Input data

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

Output data

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

Examples

Input example #1
2
1 1
1 1
Output example #1
2
1 1
2 2