当前没有测试数据。

题目描述

        蚂蚁在回家路上，他的任务自然是回家。蚂蚁在一个w*h个方格的地图上。每秒钟他能向上下左右四个方向移动一格，但不能离开地图。由于蚂蚁体能有限，每秒钟他要消耗1点HP,刚开始时他有满HP6点。他可以沿路通过进食来补满HP(即6点)，只要他走到有食物的格子，他不需要任何时间即可进食完毕。一个格子上的食物量对于小蚂蚁来说是庞大的，只要他愿意，每次经过这个格子都有吃不完的食物。

地图上有5种格子：

• 数字0:表示障碍物，蚂蚁不能走到这个格子上，更不能跨越。数字1:表示空地，蚂蚁可以自由行走
• 数字2：表示蚂蚁出发点，他也是一片空地.数字3：表示蚂蚁的家.
• 数字4：表示有食物在上面的空地.

        你能告诉蚂蚁先生他能否安全回家，如果能，最短需要多长时间呢？

输入格式

第一行，表示宽w和长h.

下面h行，每行w个数字来描述地图.

输出格式

输出一行，若蚂蚁不能回家，输出-1，否则输出蚂蚁回家所需最短时间。

样例

3 3
2 1 1
1 1 0
1 1 3

4

数据范围

• 对于 $100\%$ 的测试数据满足：$0<w,h<9$。