Геймери#1398
Вулиці та перехрестя Бухареста утворюють ідеальну ґратку. На кожному перехресті знаходиться рівно один ігровий клуб і один геймер. Кожен ігровий клуб пропонує рівно одну гру. Геймери живуть за такими правилами:
Геймер ніколи не грає у клубі на власному перехресті. Ніколи!!!
Протягом дня кожен геймер повинен зіграти у всі ігри, якщо це не суперечить Правилу 1.
Геймери переміщуються між перехрестями лише горизонтально або вертикально.
Геймер не може йти безпосередньо з одного клубу до іншого. Спочатку він повинен повернутися додому, перш ніж йти до іншого клубу, і має завершити день на власному перехресті.
Геймер завжди діє оптимально, обираючи найкращу стратегію відповідно до наведених правил, щоб мати достатньо часу для ігор.
Оскільки всі геймери однакові, Асоціація Комп'ютерних Маніяків вирішила оптимізувати місто так, щоб мінімізувати загальні негеймерські зусилля. Негеймерське зусилля — це кількість перехресть, які геймер проходить за день. Загальні негеймерські зусилля — це сума негеймерських зусиль для всіх геймерів міста. Для проведення цих оптимізацій ACM потрібна програма, що обчислює загальні негеймерські зусилля для заданого опису міста.
У стандартному введенні задано кілька описів міст. Кожен опис починається рядком з двох цілих чисел і (1 \leq R, C \leq 1000) — кількість рядків і стовпців перехресть у місті. Далі йдуть рядків по символів, які описують гру, що пропонується у кожному клубі на кожному перехресті. Кожна гра позначена однією цифрою ( до ).
Для кожного опису міста виведіть у окремому рядку загальні негеймерські зусилля для цього міста.
Приклад 1