ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1480. Талоны

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
В первый день петрозаводских сборов каждому участнику вручаются талоны на питание в столовой Петрозаводского государственного университета. Сборы в этом году длятся N2 дней, на каждый день полагается отдельный талон. Организаторы сборов поступили рационально, напечатав на листе зелёной бумаги таблицу N × N, в каждой ячейке которой стоит число от 1 до N2 — номер дня, на который распространяется действие талона. Все числа в таблице различны. Участникам предлагается разрезать лист на N2 ячеек, чтобы получить N2 талонов: по талону на каждый день сборов.
В этом году Дима, получив свой лист с талонами, обратил внимание на то, что в i-й строке и j-м столбце напечатанной таблицы стоит число N(i – 1) + j (строки и столбцы нумеруются с единицы). Соседними в таблице называются ячейки, имеющие общую сторону. Дима — математик, поэтому он сразу нашёл две соседние ячейки в таблице с наибольшей суммой чисел в них. Сумма оказалась равна 2N2 – 1. Теперь Дима хочет найти такой порядок талонов в таблице, при котором максимальная сумма чисел в двух соседних ячейках примет наименьшее значение. У Димы есть N2 дней, чтобы найти такую таблицу. Сможете ли вы сделать это за пять часов?

Исходные данные

Ввод состоит из единственного целого числа 2 ≤ N ≤ 50.

Результат

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

Пример

исходные данныерезультат
2
6
1 4
3 2
Автор задачи: Сергей Пупырев
Источник задачи: XI Чемпионат УрГУ по программированию, 7 октября, 2006