Умный Бобер следит за своим внешним видом, а особое внимание уделяет обуви, потому имеет огромное количество пар кроссовок от самых известных лесных брендов. Он старается аккуратно складывать свои ботинки, чтобы каждая пара стояла рядышком. Но к концу недели из-за достаточно активного образа жизни в его гардеробной образуется беспорядок.
Умный Бобер из ABBYY является не только самым эрудированным бобром в округе, но еще и самым хозяйственным. Например, по понедельникам Умный Бобер устраивает генеральную уборку в своем жилище.
Настало утро понедельника. Тратить на уборку весь день Умный Бобер не хочет, да еще и дел много, в тренажерный зал успеть нужно, потому желает прибраться как можно скорее. И вот полы вымыты, пыль вытерта — время прибраться в гардеробной. Но как только Умный Бобер вошел в гардеробную — все планы на день были вмиг разрушены: там царил полный хаос и казалось, что невозможно справиться даже за неделю. Обнадежьте нашего героя: подскажите ему, какое минимальное количество ботинок должно изменить свое положение, чтобы в гардеробной наступил порядок.
Гардеробная имеет прямоугольную форму и разделена на n × m равных квадратов, причем в каждом квадрате лежит ровно по одному ботинку. Каждая пара обуви пронумерована уникальным числом от 1 до 
. Квадрат с координатами (i, j) содержит целое число — номер пары, которой принадлежит ботинок, лежащий в нем. Умный Бобер считает, что в гардеробной порядок, только когда каждая пара кроссовок лежит рядом. Будем считать, что пара кроссовок в квадратах (i1, j1) и (i2, j2) лежит рядом, если |i1 - i2| + |j1 - j2| = 1.