题目描述

小H在一个划分成了 $n \times m$ 个方格的长方形封锁线上。每次他能向上下左右四个方向移动一格（当然小H不可以静止不动），但不能离开封锁线，否则就被打死了。刚开始时他有满血 6 点，每移动一格他要消耗 1 点血量。一旦小H的血量降到 0，他将死去。他可以沿路通过拾取金币来补满血量。只要他走到有金币的格子，他不需要任何时间即可拾取。格子上的金币可以瞬间补满，所以每次经过这个格子都有金币。就算到了某个有金币的格子才死去，他也不能通过拾取金币补满血。即使在家门口死去，他也不能算完成任务回到家中。

地图上有 5 种格子：

• 数字 0：障碍物。
• 数字 1：空地，小H可以自由行走。
• 数字 2：小H出发点，也是一片空地。
• 数字 3：小H的家。
• 数字 4：有金币在上面的空地。

小H能否安全回家？如果能，最短需要多长时间呢？

输入格式

第一行：两个整数 $n, m$，表示地图的大小为 $n \times m$。 接下来 $n$ 行：每行 $m$ 个数字来描述地图。

数据范围：$1 \le n, m \le 9$。

输出格式

一行，若小H不能回家，输出 -1；否则输出他回家所需最短时间。

样例 #1

样例输入 #1

3 3
2 1 1
1 1 0
1 1 3

样例输出 #1

4

样例解释 #1

小H的起点在左上角 $(1,1)$，家在右下角 $(3,3)$。 一条可行的最短路径为： $(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)$ 总步数为 4。 初始血量为 6，每走一步消耗 1 点，到达家时血量为 $6-4=2$（大于 0），因此可以安全回家。