你有一个 $n \times n$ 的棋盘。棋盘上的每个格子都有权重和颜色，权重和颜色均为正整数。行和列的编号均从 $1$ 到 $n$。令 $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。在每一步中，你可以从格子 $(i, j)$ 移动到 $(i, j+1)$ 或 $(i+1, j)$。

考虑所有从 $(1, 1)$ 到 $(n, n)$ 且遵循上述规则的路径。显然，每一条这样的路径都恰好包含 $2n - 1$ 个格子。我们将路径的权重定义为路径上所有格子权重的总和。我们将路径的“色彩度”定义为路径上所有格子所包含的不同颜色的数量。

给定所有格子的权重和颜色，请找出所有权重不超过 $W$ 的路径中，色彩度最小的路径，或者报告不存在这样的路径。

输入格式

第一行包含三个整数：$n$ ($1 \le n \le 400$)，$k$ ($1 \le k \le 10$，表示可能的颜色数量) 以及 $W$ ($1 \le W \le 10^9$)。接下来的 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行的第 $j$ 个整数表示格子 $(i, j)$ 的权重 ($1 \le w_{ij} \le 10^6$)。最后 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 行的第 $j$ 个整数表示格子 $(i, j)$ 的颜色 ($1 \le c_{ij} \le k$)。

输出格式

第一行输出路径的最小色彩度。第二行输出该最小色彩度路径的坐标，格式为 $i_1 \ j_1 \ i_2 \ j_2 \ \dots \ i_{2n-1} \ j_{2n-1}$。如果存在多条色彩度相同的路径，输出其中任意一条即可。如果不存在权重不超过 $W$ 的路径，则单独输出 $-1$。

样例

样例输入 1

3 3 10
1 1 1
5 3 1
5 3 1
1 2 3
2 2 1
3 3 2

样例输出 1

2
1 1 1 2 2 2 2 3 3 3

样例输入 2

1 1 1
2
1

样例输出 2

-1

样例输入 3

2 6 1000
10 10
1 10
1 1
2 1

样例输出 3

1
1 1 1 2 2 2

说明

在第一个样例中，路径 $(1, 1) - (1, 2) - (2, 2) - (2, 3) - (3, 3)$ 的权重为 $1 + 1 + 3 + 1 + 1 = 7 \le W$，其色彩度为 $2$。显然不存在色彩度为 $1$ 的路径。

在第二个样例中，唯一的路径权重为 $2 > W$，因此答案为 $-1$。