<table border=0>
<tr>
<td width="80%">
EJOI 2020 Day 2 </br>
<b>game</b> (Slovene)
</td>
<td width="20%">
<img align="right" width="100" src="https://i.imgur.com/KUVHoM0.png">
</td>
</tr>
</table>

# Pike in kvadrati

Sestri Tamta in Anna se radi igrata igro Pike in kvadrati. Igra se začne s prazno mrežo pik velikosti $(N+1) \times (M+1)$ (na mrežo lahko gledamo tudi kot mrežo oglišč $N \times M$ kvadratov). Igralki izmenično dodajata navpični ali horizontalni rob med dvema nepovezanima sosednjima pikama (piki sta sosednji, če je razdalja med njima enaka $1$). Če igralka uspešno dokonča kvadrat velikosti $1 \times 1$, si prisvoji kvadrat, dobi točko in **naredi naslednjo potezo**. Če ji ne uspe dokončati kvadrata, je na potezi njena sestra. Igra se konča, ko ni moč postaviti nobenega roba več.

*Spodaj na sliki so možne poteze v naslednjih treh korakih ($N = 2$ in $M = 3$) (pikčaste črte predstavljajo naslednjo potezo):*


Anna in Tamta sta že sredi igre, ko opaziš, da je trenutno stanje na mreži takšno, da **vsak kvadrat bodisi nima robov, bodisi ima natanko dva robova in, da je na potezi Anna.** (Primer je na spodnji sliki, slika zgoraj ne ustreza temu opisu.)

Rezultat igre se izračuna kot $S_A - S_T$, kjer je $S_A$ število točk, ki jih doseže Anna od tega trenutka naprej in $S_T$ število točk, ki jih doseže Tamta. Izračunaj rezultat igre, če veš, da obe igralki igrata optimalno.

## Vhod

V prvi vrstici vhoda se nahajata celi števili $N$ in $M$, ki predstavljata število vrstic in stolpcev na mreži kvadratov.

V vsaki od naslednjih $N+1$ vrstic se nahaja $M$ števk, ki niso ločene s presledkom, zavzamejo pa lahko le vrednosti $0$ in $1$. $j$-ta števka v $i$-ti vrstici je enaka $1$ le, če sta piki s koordinatami $(i, j)$ in $(i, j+1)$ vodoravno povezani.

Temu sledi $N$ vrstic, ki vsebujejo $M+1$ števk v enaki obliki. Torej: $j$-ta števka v $i$-ti vrstici je enaka $1$ le, če sta piki s koordinatami $(i, j)$ in $(i+1, j)$ navpično povezani.

## Izhod

Na izhod izpiši vrstico s celim številom - rezultatom igre.

## Omjeitve

* $3 \leq N, M \leq 20$
* **vsak kvadrat bodisi nima robov, bodisi ima natanko dva robova**

## Podnaloge

Definirajmo komponento kot največjo povezano množico nikogaršnjih kvadratov na mreži. Na spodnji sliki lahko vidiš $5$ razičnih komponent.


1. podnaloga (20 točk): V igri je preostala le še ena komponenta.
2. podnaloga (20 točk): $N \cdot M \leq 12$
3. podnaloga (20 točk): V igri sta preostali le še dve komponenti.
4. podnaloga (20 točk): $N \leq 7$, $M \leq 7$.
5. podnaloga (20 točk): Ni dodatnih omejitev.

## Primeri

### 1. primer

#### Vhod

3 3
000
111
011
110
1010
1000
1001

#### Izhod

-5

### 2. primer

#### Vhod

5 5
00100
10100
11010
00100
01000
11100
011111
001011
101011
110111
100111

#### Izhod

6

V prvem primeru je eno izmed možnih optimalnih sosledij potez orisano na spodnji sliki. (Število na robu označuje vrstni red potez, rdeča barva označuje Annine poteze, modra barva pa označuje Tamtine poteze).


Drugi primer je prikazan na sliki v poglavju Podnaloge.