2. Uzimený večer

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.