infectie

Extinction is the rule. Survival is the exception.
Carl Sagan

Cerință

Este anul 4924 și umanitatea a reușit să colonizeze o bună parte a galaxiei. Planeta Aurora este casa uneia dintre cele mai dezvoltate civilizații din toată galaxia, iar conducătorul ei, Dr. Kelden Amadiro are planuri malefice pentru planeta-mamă, Terra. Suprafața Terrei este delimitată în teritorii care formează un grid cu $N$ linii și $M$ coloane, fiecare teritoriu identificându-se printr-o pereche $(i,j)$, unde $i$ este indicele liniei, iar $j$ indicele coloanei. Amadiro a dezvoltat un virus care poate să eradice populația unui teritoriu într-o singură zi. Virusul se răspândește de la teritoriu la teritoriu în următorul mod: dacă un teritoriu $(i,j)$ este vecin pe latură cu cel puțin două teritorii infectate, atunci și el devine infectat. Cum crearea virușilor în laborator este o muncă foarte complicată și costisitoare, Amadiro se întreabă care este numărul minim de teritorii care trebuie infectate, astfel încât virusul să se răspândească într-un final peste toate teritoriile Terrei.

Date de intrare

Pe prima linie se găsesc dimensiunile Terrei, $N$ și $M$.

Date de ieșire

Pe prima linie se va găsi un singur număr natural, reprezentând numărul minim de teritorii ce trebuie infectate astfel încât toată planeta să ajungă infectată.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000 \ 000 \ 000$
• Pentru teste în valoare de $10$ puncte, $N=1$ și $1 \leq M \leq 100 \ 000$
• Pentru teste în valoare de $15$ puncte, $N=2$ și $1 \leq M \leq 100 \ 000$
• Pentru teste în valoare de $25$ puncte, $1 \leq N,M \leq 500$

Exemplul 1

stdin

2 2

stdout

2

Explicație

Putem infecta inițial teritoriile $(1, 1)$ și $(2, 2)$.
Teritoriul $(1, 2)$ este vecin pe latură cu ambele (are vecinii infectați la stânga și jos), așa că va deveni infectat. Similar, teritoriul $(2, 1)$ are și el doi vecini infectați (sus și dreapta) și va deveni infectat. Astfel, cu $2$ teritorii inițiale, tot gridul este infectat.
Un singur teritoriu infectat inițial nu s-ar putea răspândi deloc.

Exemplul 2

stdin

1 4

stdout

3

Explicație

Într-un grid $1 \times 4$, teritoriile de la capete ($(1, 1)$ și $(1, 4)$) au un singur vecin. Deoarece pentru a se infecta prin răspândire un teritoriu necesită doi vecini infectați, capetele nu pot fi niciodată infectate de la altele, deci trebuie infectate inițial.
Dacă infectăm doar $(1, 1)$ și $(1, 4)$, teritoriile din mijloc ($(1, 2)$ și $(1, 3)$) vor avea doar câte un vecin infectat, deci virusul nu se va răspândi.
Suntem obligați să mai infectăm un teritoriu inițial, de exemplu pe $(1, 2)$. Astfel, teritoriul $(1, 3)$ are acum vecinii $(1, 2)$ și $(1, 4)$ infectați și va fi și el infectat, acoperind toată harta cu un total de $3$ teritorii alese inițial.