动态lcm

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

给定N×M的矩阵,其中的每个元素都是1到50之间的整数。你的任务是从左上角(1,1)走到右下角(N,M),每一步只能够向右或者向下,并且不能够走出矩阵的范围。你所经过的方格里面的数字都必须被选取,请找出一条最合适的道路,使得在路上被选取的所有数字的LCM(最小公倍数)为尽可能小的正整数。

Input

输入第1行是两个整数M和N(2<=M<=5,2<=N<=5),分别表示矩阵的行和列的数目。接下来N行,每行包括M个整数,就是矩阵中的每一行的M个元素。

Output

输出只有一行,就是一个整数,表示所选道路上数字的LCM(最小公倍数)所能达到的最小正整数。

Sample Input

2 2
1 2
3 4

Sample Output

4

Hint

Source

【2017级《程序设计基础(B)II》期末上机考试】Fish_li