P3786 萃香抱西瓜

 伊吹萃香 (Ibuki Suika) 正在魔法之森漫步，突然，许多西瓜 (Suika) 从四周飞来，划出了绚丽的轨迹。虽然阵势有点恐怖，但她还是决定抱走一些西瓜。

萃香所处的环境被简化为一个长为 $h$，宽为 $w$ 的网格平面。$X$ 坐标范围为 $[1,w]$，$Y$ 坐标范围为 $[1,h]$。 她初始时（第 $1$ 个时刻）站在坐标为 $(sx,sy)$ 的方格。 西瓜可能在任意一个方格出现，在每个时间单位，它们可能向任何一个方向移动，也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为 $n$ 个，但只有 $m$ 个西瓜可以被萃香抱走，因为其他都太大了，可能会砸伤她。 整个过程会持续 $T$ 个时刻。萃香希望可以抱走全部的 $m$ 个西瓜，并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻，与该西瓜处于同一位置。另外，由于萃香不愿耗费过多体力到处乱跑，她每个时刻可以选择静止不动，也可以选择移动到相邻的四个格子之一，只要不越出环境边界。如果选择移动到相邻格子，则算作移动了一次。第 $1$ 个时刻萃香刚站定，无法移动。 在每个时刻，如果萃香选择移动，可以认为萃香与西瓜同时从原来的位置移到了新的位置，没有先后顺序。 萃香想要知道，不被任何一个大西瓜砸中，并得到所有的m个小西瓜的情况下，最少需要移动多少次。

无

无

### 样例说明 第 $2 \sim 4$ 个时刻萃香站着不动，在第 $6$ 个时刻，西瓜出现在萃香旁边，萃香移动到 $(3,4)$ 位置即可抱走这个西瓜。 ### 数据范围和提示 本题采用捆绑测试。 Subtask $1$：具有特殊性质 A 和 B； Subtask $2 \sim 3$：仅具有特殊性质 A； Subtask $4 \sim 5$：仅具有特殊性质 B； Subtask $6 \sim 10$：不具有任何一个特殊性质。 特殊性质 A：对于所有西瓜，均满足 $t1=1,t2=T+1$。 所有西瓜全程都静止在原地，不会发生移动。 特殊性质 B：$m=0$。 对于全部子任务，满足： $1 \le x \le w,1 \le y \le h$ $1\le n \le 20, 0 \le m \le 10, m \le n$ $1 \le h,w \le 5, 1 \le T \le 100, 1 \le t1 \le T, 2 \le t2 \le T+1, t1< t2$ 保证一个位置不会同时出现两个或两个以上西瓜。