Головоломка

Задано N^2 десяткових цифр від 1 до 9.

Розглянемо розміщення цих цифр у клітинках квадратної таблиці N×N, по одній цифрі у клітинці. У кожному з рядків таблиці, рахуючи зліва праворуч, отримаємо десятковий запис деякого N-значного числа. У кожному зі стовбців таблиці, рахуючи зверху до низу, також отримаємо десятковий запис деякого N-значного числа. Нехай S — це сума усіх N чисел по рядкам і усіх N чисел по стовбцям.

Розмістіть числа всередині таблиці таким чином, щоб значення S було максимальним.

Вхідні дані

Перший рядок вхідного файлу містить ціле число N. У другому рядку записано без відокремлень N^2 десяткових цифр від 1 до 9. Число N ціле (1 ≤ N ≤ 8).

Вихідні дані

Виведіть максимально можливе значення суми S.

Приклади