Стена для состоит из M рядов по N одинаковых кирпичей в каждом. Каждый последующий ряд смещен относительно предыдущего на 1/2 кирпича (см. рисунок). Четные ряды сверху смещаются влево, а нечетные - вправо. Конфигурация из кирпичей является устойчивой, если каждый кирпич опирается, по крайней мере, на один кирпич в нижележащим ряду. Очевидно, что из заданной конструкции можно удалить некоторые кирпичи без потери ее устойчивости. На втором рисунке изображен пример возможной конструкции для стены на первом рисунке.

Написать программу, которая по заданным M и N (0 < M, N ≤ 1000) и находит конструкцию, получающуюся из исходной путем удаления по возможности максимального количества кирпичей, чтобы верхний ряд остался без изменения, а конструкция не потеряла устойчивость.

Входной файл с именем INPUT.TXT содержит количество рядов M и ширину стены N.

В выходной файл с именем OUTPUT.TXT вывести количество оставшихся кирпичей и конфигурацию стены. Оставшиеся кирпичи перечисляются начиная с верхнего ряда, слева направо в каждом ряду (нумерация в каждом ряду начинается с единицы). Список кирпичей каждого ряда должен заканчиваться числом 0. Все числа в выходном файле должны разделяться пробелами и (или) символами перевода строки.

input.txt	output.txt
4 5	13 1 2 3 4 5 0 2 4 5 0 2 3 5 0 3 5 0

• Задача оценивается в 33 балла.
• Программы, выдающие правильные, но не оптимальные решения также будут оцениваться.
• Время тестирования ограничено 1 минутой.