Keď Emo pozrel von z okna a uvidel sneh, zmenil svoje plány a rozhodol sa, že päty z izby nevystrčí. Povedal si, že tento dlhý zimný večer strávi pri partičke šachu s so svojím spolubývajúcim Marcelom. Jediná šachovnica, ktorú zohnali, však bola pomaľovaná všetkými možnými farbami, a tak sa nedokázali sústrediť. Rozhodli sa preto, že ju opravia.

Zohnali si fixy všetkých potrebných farieb a povedali si, že niektoré políčka prefarbia tak, aby výsledná šachovnica bola iba dvojfarebná a farby políčok sa striedali ako biele a čierne na šachovnici. Keďže si ale fixky požičali, chcú ich čo najmenej vypísať. Koľko najmenej políčok musia prefarbiť tak, aby dostali peknú šachovnicu?

Úloha

Máme zadanú šachovnicu veľkosti $n \times n$, ktorej každé políčko má nejakú farbu. Zistite, koľko najmenej políčok je potrebné prefarbiť tak, aby políčka šachovnice obsahovali iba $2$ rôzne farby, ktoré sa striedajú horizontaĺne aj vertikálne (tak ako biele a čierne políčka na šachovnici).

Formát vstupu

Farby si budeme reprezentovať celými číslami. V prvom riadku vstupu je jedno celé číslo $n$ ($1 \leq n \leq 500$) – rozmer šachovnice. Nasleduje $n$ riadkov, každý z nich obsahuje $n$ medzerou oddelených celých čísel – $j$-te číslo v $i$-tom riadku vstupu označuje farbu políčka v $i$-tom riadku a $j$-tom stĺpci šachovnice. Môžete predpokladať, že všetky čísla sú medzi $0$ a $(n ^{2}-1)$.

Formát výstupu

Vypíšte jeden riadok obsahujúci jedno číslo – najmenší počet políčok, ktoré je potrebné zmeniť.

Hodnotenie

Riešenia budú testované na štyroch sadách testovacích vstupov, pre jednotlivé sady platia nasledovné obmedzenia:

Príklady

Input:

4 
1 2 1 3
2 1 2 2
3 1 2 5
5 4 2 1

Output:

8

Zmenením vhodných $8$ políčok vieme dostať nasledovnú šachovnicu:

`1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1`

Input:

5
6 3 6 1 6
3 6 1 6 3
6 1 6 1 6
3 6 1 6 3
6 3 6 1 6

Output:

6

Buď prefarbíme všetky jednotky na trojky, alebo všetky trojky na jednotky. V oboch prípadoch musíme opraviť $6$ políčok.