相信大家都玩过贪食蛇游戏，现在有一个改版贪食蛇游戏，跟传统的贪食蛇游戏一样，贪食蛇在活动区域内运动，吃食物，但是这个改版的贪食蛇游戏有着一些特别的规则。
活动区域：
贪食蛇的活动区域是一个 行 列的网格 ，贪食蛇活动不能超过这个网格的范围。第 行第 列的方格用 表示。每个方格有一个整数权值，记作 。 时， 禁止进入； 时， 允许进入。
方向：
对于，，有以下四种基本方向：
-
正左 ： 且 ，则称 位于 的正左方向。
-
正右 ： 且 ，则称 位于 的正右方向。
-
正上 ： 且 ，则称 位于 的正上方向。
-
正下 ： 且 ，则称 位于 的正下方向。
贪食蛇：
贪食蛇 是占据若干方格的图形，占据的方格数为贪食蛇的长度，记为 ，则贪食蛇从头到尾，用 表示。记 为贪食蛇的形态，若 位于第 行第 列，则 。初始情况下，，且运动过程中始终需要满足以下限制：
食物：
贪食蛇的活动区域内存在一些食物。每个食物位于一个允许进入的方格上，食物不会重叠。每个食物只能被吃一次。
贪食蛇的运动：
如果贪食蛇的头部 的 四个方向之一的 能进入，且 上不存在食物，则贪食蛇可以向该方向运动，新的头部位于 上。记 为贪食蛇新的形态，则：
贪食蛇的进食：
如果贪食蛇的头部 的 四个方向之一的 能进入，且 上存在食物，则贪食蛇可以向该方向进食，新的头部位于 上，蛇的新长度 。记 为贪食蛇新的位置，则：
注意：运动或进食后的贪食蛇形态，仅仅需要考虑变换后的形态是否满足限制，不需要考虑变换的过程。也就是说，原来形态合法的贪食蛇的头部可以运动到尾部的位置，因为在变换后头部和尾部仍不会重叠。
运动或进食所需要的时间：
贪食蛇运动或进食，需要消耗时间。设运动或进食前头部所在的方格是 ，运动或进食后头部所在的方格是 ，则此次运动或进食的所消耗的时间为 。
游戏的会在开始前给出贪食蛇的初始位置和所有食物的位置。你的任务是，以最少的时间令贪食蛇吃完所有食物。
