U605417 密码迷宫

在古老的数字王国中，传说存在一座由密码守护的迷宫。这座迷宫的每一个房间都刻有一个神秘的数字，而连接房间的通道则受到数论法则的约束。只有十分聪明的人，才能成功穿越迷宫，找到最终的宝藏。

密码迷宫可以抽象为一个 $n \times m$ 的网格，每个格子 $(i,j)$ 上有一个整数 $a_{i,j}$。迷宫的入口在左上角 $(1,1)$，出口在右下角 $(n,m)$。玩家需要从入口出发，通过移动到相邻的格子（上、下、左、右四个方向），最终到达出口。 在迷宫中移动需要遵守以下规则： 1. 从格子 $(x_1,y_1)$ 移动到格子 $(x_2,y_2)$ 时，必须满足 $a_{x_1,y_1}$ 与 $a_{x_2,y_2}$ 的最大公约数大于 $1$。 2. 玩家在迷宫中走过的所有格子（包括入口和出口）的数字必须能组成一个递增序列（即路径上所有格子的数字按经过顺序排列后，后一个数字必须严格大于前一个数字）。 现在需要聪明的你来计算从入口到出口的所有合法路径中，路径上所有数字的乘积的最大值。如果不存在合法路径，则输出 $-1$。

第一行包含两个整数 $n, m$，表示迷宫的大小。 接下来 $n$ 行，每行 $m$ 个整数，表示网格中每个格子的数字 $a_{i,j}$。

输出一个整数，表示所有合法路径中数字乘积的最大值。若不存在合法路径，则输出 $-1$。

**本题采用捆绑测试**。 - Subtask 1（20 points）：$1 \leq n, m \leq 20$，$1 \leq a_{i,j} \leq 5$。 - Subtask 2（30 points）：$21 \leq n, m \leq 35$，$1 \leq a_{i,j} \leq 10$。 - Subtask 3（20 points）：$36 \leq n, m \leq 50$，$1 \leq a_{i,j} \leq 100$。 - Subtask 4（30 points）：$51 \leq n, m \leq 70$，$1 \leq a_{i,j} \leq 250$。 对于所有测试数据，$1 \leq n, m \leq 70$，$1 \leq a_{i,j} \leq 250$。