问题描述

在数学王国中有一个大小为 $N \times M$ 的二维矩阵，对于矩阵中任意的 $1 \leq i \leq N, 1 \leq j \leq M$ 都有一个正整数 $A_{i, j}$。

小蓝起初在位置 $(1, 1)$ ，并持有 $Q$ 把密匙。小蓝每次可以向右或向下移动，当小蓝所在位置的数和移动的目的地的数 不互质 时，不消耗密匙；否则需要消耗一把密匙，没有密匙则无法通行。

具体的，小蓝在位置 $(i, j)$ 时，当 $gcd(A_{i, j}, A_{i + 1, j}) \neq 1$ 时，抵达 $(i + 1, j)$ 不消耗密匙，否则需要消耗一把密匙；当 $gcd(A_{i, j}, A_{i, j + 1}) \neq 1$ 时，抵达 $(i, j + 1)$ 不消耗密匙，否则需要消耗一把密匙。

求当抵达 $(N, M)$ 时所经过的路径上的数值之和，并使这个数最大。无法抵达时输出 $-1$。

输入格式

输入一行包含 $3$ 个数 $N, M, Q$ 分别为矩阵的大小和密匙的数量。

接下来输入 $N$ 行，每行 $M$ 个数，为矩阵上的数值 。

输出格式

输出仅一行，包含一个整数，表示答案。

样例输入

3 3 1
2 6 7
1 3 9
5 6 8

样例输出

28

说明

在样例中，最优路径为 $(1,1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)。$

在 $(2, 3) \rightarrow (3, 3)$ 时消耗一把钥匙。

评测数据规模

$1 \leq N, M \leq 1000$。

$0 \leq Q \leq 3$。

$1 \leq A(i, j) \leq 10^9$。