\documentclass[12pt]{article}
\input{structure.tex}
\fancyhead[R]{
	\begin{minipage}{\textwidth}
		\raggedleft
		\includegraphics[width=2cm]{./logo2.png}
	\end{minipage}
}
\renewcommand{\bottomtitlespace}{3cm}

\begin{document}
\renewcommand{\tl}{$0.1$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача OS10. ТРИ}
\addauthor{Автор: Божан Иванов (заета)}{2026}{08}{29}
\renewcommand{\header}{
	НАЦИОНАЛНА ШКОЛА ПО ИНФОРМАТИКА\\
	ОТБОРНО СЪСТЕЗАНИЕ\\
	Габрово, 29 август 2026 г.\\
	8 – 10 клас
}

Ели има правоъгълна матрица с $N$ реда и $M$ колони. Всяка клетка съдържа по една цифра $(\texttt{0}-\texttt{9})$. Момичето дефинира "път"{} от клетката в горния ляв ъгъл (ред $1$, колона $1$) до тази в долния десен ъгъл (ред $N$, колона $M$) като последователност от съседни (споделящи стена) клетки, движейки се само надолу и надясно. Всеки път има "стойност"{} – това е числото, което се образува като долепим цифрите от посетените клетки, в реда, в който ги посещаваме. Стойности с водещи нули са разрешени. Нека разгледаме следната матрица с $4$ реда и $7$ колони:
\begin{center}
\texttt{1849312}\\
\texttt{8951400}\\
\texttt{5678129}\\
\texttt{8721365}
\end{center}

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

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

Ели иска да получи матрица, в която всички пътища имат стойности, които се делят на три. Разбира се, тя иска да постигне това с минимален брой операции. Напишете програма \textbf{\texttt{three}}, която намира този минимален брой.

\subsection{Вход}
На първия ред на стандартния вход ще бъдат зададени двете цели числа $N$ и $M$ -- съответно броя редове и колони на матрицата. На всеки от следващите $N$ реда ще има по една последователност от $M$ цифри $(\texttt{0}-\texttt{9})$.

\subsection{Изход}
На единствен ред на стандартния изход изведете едно цяло число -- минималния брой операции, който е достатъчен за да се промени матрицата в такава, в която всеки път от горния ляв до долния десен ъгъл има стойност, деляща се на три.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N, M \leq 50$
\end{itemize}

\subsection{Пример}
\begin{table}[H]
	\begin{tblr}{|l|l|}
		\hline
		\textbf{Вход} & \textbf{Изход} \\
		\hline
		\texttt{\makecell[lt]{
			4 7\\
			1849312\\
			8951400\\
			5678129\\
			8721365
		}}
		&
		\texttt{\makecell[lt]{
			10
		}} \\
        \hline
	\end{tblr}
\end{table}

\end{document}