Матриця

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

Вхідні дані

Перший рядок вхідного файлу містить одне ціле число n (1 ≤ n ≤ 239). Наступні n рядків містять по n цілих чисел у кожному. Усі ці числа не перевищують по абсолютній величині 10^6.

Втхідні дані

Перший рядок повинен містити значення оптимізуючої функції. У наступні n рядків необхідно записати пари чисел, які описують вибрані комірки. Першою координатою виводиться номер рядка.

Приклади