正文

现有一个大小为n*m的棋盘，上有k枚棋子.规定：棋盘上的每个格子都只能放至多1枚棋子.现在对棋盘上的所有棋子进行如下操作：

①：将所有棋子同时向上或向下移动一格，上下可任意自选，但所有棋子只能同上或同下

②：将所有棋子同时向左或向右移动一格，左右可任意自选，但所有棋子只能同左或同右

同时，两种操作只能交替进行，即既可以按照①②①②①②①...的顺序操作，也可以按照②①②①②①②...的顺序操作。显然，第一次操作确定后，后面每次操作的选择是固定的。

如果若干次操作后，有棋子无论怎么操作都会超出棋盘范围或与其他棋子重叠于同一格，则视为操作失败。 现在给定正整数n,m，求一个最大的k，使得操作可以进行无穷多次也不会失败。

数据规模

$1≤n,m≤10^{100}.$要用高精度.

样例数据

2 2

1

1111111111111111111111112
2222222222222222222222223

2469135802469135802469135308641975308641975308642