Умный Бобер следит за своим внешним видом, а особое внимание уделяет обуви, потому имеет огромное количество пар кроссовок от самых известных лесных брендов. Он старается аккуратно складывать свои ботинки, чтобы каждая пара стояла рядышком. Но к концу недели из-за достаточно активного образа жизни в его гардеробной образуется беспорядок.

Умный Бобер из ABBYY является не только самым эрудированным бобром в округе, но еще и самым хозяйственным. Например, по понедельникам Умный Бобер устраивает генеральную уборку в своем жилище.

Настало утро понедельника. Тратить на уборку весь день Умный Бобер не хочет, да еще и дел много, в тренажерный зал успеть нужно, потому желает прибраться как можно скорее. И вот полы вымыты, пыль вытерта — время прибраться в гардеробной. Но как только Умный Бобер вошел в гардеробную — все планы на день были вмиг разрушены: там царил полный хаос и казалось, что невозможно справиться даже за неделю. Обнадежьте нашего героя: подскажите ему, какое минимальное количество ботинок должно изменить свое положение, чтобы в гардеробной наступил порядок.

Гардеробная имеет прямоугольную форму и разделена на n × m равных квадратов, причем в каждом квадрате лежит ровно по одному ботинку. Каждая пара обуви пронумерована уникальным числом от 1 до . Квадрат с координатами (i, j) содержит целое число — номер пары, которой принадлежит ботинок, лежащий в нем. Умный Бобер считает, что в гардеробной порядок, только когда каждая пара кроссовок лежит рядом. Будем считать, что пара кроссовок в квадратах (i₁, j₁) и (i₂, j₂) лежит рядом, если |i₁ - i₂| + |j₁ - j₂| = 1.