Задача F. Круговая оборона

Автор:А. Кленин, Т. Чистяков   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

У государства Централии есть четыре агрессивных соседа: Верхия, Низия, Правия и Левия. Правители соседних государств постоянно сосредотачивают на границе с Централией свои армии, ожидая удобного случая для вторжения. Удобным агрессоры считают случай, когда количество армий Централии, охраняющих границу с данным государством, будет меньше, чем количество армий, сосредоточенных на границе агрессором.

Поскольку содержание армий — дорогостоящее занятие, Централия может постоянно поддерживать только N армий. К счастью, по той же причине её соседи, чья экономика менее стабильна, чем в Централии, могут в i-й год подготовить для завоевания Ai,k армий, где k = 0… 3 — номер соседа.

В Централии проживает могущественный колдун-экономист, который сумел предсказать количество враждебных армий на T лет вперёд. Вам поручена роль главнокомандующего армиями Централии с задачей распределения армий по границам таким образом, чтобы удобный для вторжения случай предоставился как можно позже. Задача осложняется тем, что за один год любая армия Централии может переместиться с той границы, которую она занимала в прошлом году, только на соседнюю границу, т.е. с k-й границы либо на границу (k + 1)mod 4, либо на границу (k + 3)mod 4.

Формат входного файла

Во входном файле находятся числа N T, за которыми следует T четвёрок чисел Ai,0 Ai,1 Ai,2 Ai,3 — количество армий, которые будут выставлены в i-м году каждым из соседних государств.

Формат выходного файла

В выходном файле должно содержаться число Q — максимальное количество лет, в течение которого можно избежать вторжения (0 ≤ Q ≤ T), за которым следуют Q четвёрок чисел Bi,0 Bi,1 Bi,2 Bi,3 — количество армий, которые следует в i-м году расположить на каждой из границ (Bi,0 + Bi,1 + Bi,2 + Bi,3 = N). Расположение защищающихся армий в первом году может быть произвольным, а расположение в каждом следующем году должно учитывать ограничения на перемещение армий.

Если существует несколько оптимальных решений, вывести любое из них.

Ограничения

1 ≤ N ≤ 10, 1 ≤ T ≤ 1000, 0 ≤ Ai, j ≤ N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2
0 4 0 0
2 1 1 0
2
0 4 0 0
2 1 1 0
2
4 2
0 4 0 0
2 0 1 1
1
0 4 0 0

0.041s 0.007s 15