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

1124. Мозаика

Ограничение времени: 0.25 секунды
Ограничение памяти: 64 МБ
Несомненно, одно из самых важных и ответственных дел, которые существуют в нашем мире — это воспитание детей. Возможно, если вы будете хорошо учиться и покажете высокие результаты на этом соревновании, вас примут в детский сад нянечкой. Но вы должны быть хорошо подготовлены к принятию такой ответственной должности! Рассмотрим типичные задачи, которые приходится решать каждой нянечке в детском саду.
Всем знакома детская игра «мозаика», где можно выкладывать картинки из разноцветных кусочков. Пусть имеется М разных цветов и по N кусочков мозаики каждого цвета. Поиграв мозаикой, дети редко разбирают все кусочки правильно, так чтобы каждый кусочек лежал в коробочке того же цвета. Этим приходится заниматься нянечке.
Для облегчения вашей задачи дети уже разложили мозаику в коробочки, в каждую коробочку по N кусочков. Но некоторые (а может и все) кусочки оказались в коробочках не своего цвета. За одно движение руки можно или переложить один кусочек из коробки в коробку, или просто перенести руку к другой коробочке. Начинать разбор можно с любой коробочки. Движение руки к первой коробочке не считается ходом. Определите, какое наименьшее количество движений руки придётся сделать, чтобы разложить все кусочки мозаики в свои коробочки.

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

В первой строке записаны целые числа 2 ≤ M ≤ 500 (число цветов) и 2 ≤ N ≤ 50 (число кусочков каждого цвета). Каждая из следующих M строк содержит N целых чисел в диапазоне от 1 до M — цвета кусочков мозаики, лежащих в данной коробочке.

Результат

Минимально возможное количество движений руки, которое надо сделать чтобы разложить все кусочки по своим коробочкам.

Пример

исходные данныерезультат
4 3
1 3 1
2 3 3
1 2 2
4 4 4
6
Автор задачи: Станислав Васильев
Источник задачи: VI Ural State University Collegiate Programming Contest (21.10.2001)