Three
TopCoder TCO2020, North America Regional
Time Limit: 0.2s, Memory Limit: 64MiB
Ели има правоъгълна матрица с N реда и M колони. Всяка клетка съдържа по една цифра (0-9). Момичето дефинира "път" от клетката в горния ляв ъгъл (ред 1, колона 1) до тази в долния десен ъгъл (ред N, колона M) като последователност от съседни (споделящи стена) клетки, движейки се само надолу и надясно.

Всеки път има "стойност" – това е числото, което се образува като конкатенираме цифрите от посетените клетки, в реда, в който ги посещаваме. Стойности с водещи нули са разрешени. Нека разгледаме следната матрица с 4 реда и 7 колони:
1849312
8951400
5678129
8721365

Пътят надолу, надясно, надясно, надолу, надясно, надясно, надясно, надолу, надясно има стойност 1895781265. Други възможни пътища са със стойности 1849312095, 1895781365, и 1858721365, (сред много други).

Момичето може да променя (потенциално всички или никоя) от клетките на матрицата. Ако текущата цифра в дадена клетка е X, с една операция Ели може да я промени или на X-1 или на X+1. Цифрите се ротират циклично между 0 и 9 – тоест, можем да променим 0 на 9 или пък 9 на 0 в една операция. Момичето може да направи колкото операции иска – тоест, може да достигне всяка възможна матрица от цифри с дадените размери.

Ели иска да получи матрица, в която всички пътища имат стойности, която се дели на три. Разбира се, тя иска да постигне това с минимален брой операции.
Вход
На първия ред на стандартния вход ще бъдат зададени двете цели числа N и M – съответно броя редове и колони на матрицата. На всеки от следващите N реда ще има по една последователност от M цифри ('0'-'9').
Изход
На единствен ред на стандартния изход изведете едно цяло число – минималния брой операции, който е достатъчен за да се промени матрицата в такава, в която всеки път от горния ляв до долния десен ъгъл има стойност, деляща се на три.
Ограничения
  • 1 ≤ N, M ≤ 50
Примерен Вход Примерен Изход
4 7 1849312 8951400 5678129 8721365 10
Примерна матрица:
1839421
8961510
6678139
9721365
Мрън!