eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Максимальне число

Максимальне число

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Задано таблицю цифр розміром N×N. Відмітимо у ній N елементів таким чином, щоб у кожному рядку та кожному стовбцю було відмічено рівно один елемент.

Далі складемо з усіх відмічених цифр число так, що його першою цифрою взято цифру, відмічену у першому рядку, другою – у другому, і так далі.

Наприклад, з відмічених у наступній таблиці цифр ми таким чином отримаємо число 4307:

Визначіть, яке максимальне число можна отримати вищеописаним способом з заданої таблиці.

Вхідні дані

Перший рядок містить ціле число N (2N100). Далі йде сама таблиця - кожен з наступних рядків містить N цифр без пропусків чи яких-небудь інших разділювачів. Цифри у таблиці від 0 до 9 включно.

Вихідні дані

Виведіть максимальне число, яке можна отримати з заданої таблиці. Не пропускайте ведучих нулів (ди. приклад № 2).

Приклад

Вхідні дані #1
4
2421
3420
1300
8187
Вихідні дані #1
4308
Автор Ніколоз Джімшелеішвілі
Джерело Зимова школа, Харків 2009, контест Теодора Заркуа та його учнів