Hədiyyə

Giriş

Birinci sətir iki tam ədəd $n$ və $m$ (1 \le n, m \le 5000) - matris $A$-nın ölçüləri. Sonrakı $n$ sətir $m$ ədəd a_{i,j} (0 \le a_{i,j} \le 1) - matris $A$-nın dəyərlərini ehtiva edir.

Çıxış

Bir tam ədəd çıxarın - minimum əməliyyatların sayını.

Əgər cavab yoxdursa, $-1$ çıxarın.

Nümunələr

Qeyd

İkinci test üçün:

Aşağıdakı çevrilmələri edə bilərik:

\begin{smallmatrix} 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 \end{smallmatrix} $\to$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} 2-ci sütunu tərsinə çevirərək

\begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} $\to$ \begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} 2-ci sətiri tərsinə çevirərək.

\begin{smallmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \end{smallmatrix} matris üçün gözəllik şərti yerinə yetirilir. Bu, ən kiçik cavab olduğunu sübut etmək olar.

Bal hesablama

1. Alt tapşırıq $1$ ($20$ bal) : (n, m \le 10)

2. Alt tapşırıq $2$ ($15$ bal) : (n = 1)

3. Alt tapşırıq $3$ ($45$ bal) : (n, m \le 100)

4. Alt tapşırıq $4$ ($80$ bal) : (n, m \le 500)

5. Alt tapşırıq $5$ ($140$ bal) : Əlavə məhdudiyyətlər olmadan