CF1214D Treasure Island

我们都喜爱宝藏，对吧？这就是为何年轻的 Vasya 正在向一个宝藏岛进发。 宝藏岛可以看做一个$n \times m$的矩阵，行从上到下标号为$1..n$，列从左到右标号为$1..m$。Vasya 现在在第$1$行，第$1$列，而宝藏位于第$n$行，第$m$列。 宝藏岛上有些位置是可以通过的空地，而其他位置是不可经过的丛林。 现在 Vasya 正急着寻找宝藏。他可以从第$i$行，第$j$列走到第$i+1$行，第$j$列或第$i$行，第$j+1$列，即，可以向下或向右走。当然他不能通过丛林区域。 邪恶的女巫不想让 Vasya 得到宝藏。她可以用魔法使得一块空地变成丛林。当然，她不能对第$1$行，第$1$列或第$n$行，第$m$列施法。 请计算女巫至少需要将几块丛林变成空地，才能完全阻止 Vasya 获得宝藏。

无

无

$3 \leq n \times m \leq 10^6$