记得玩过一个游戏，大意是说一个外星小精灵（具体名字我忘了，在这里我们暂且称其为 Bob）被困在地球的一片树林内，树林里有各种各样的怪物，你必须帮助 Bob 尽快逃离森林。 
现在，我们将这个问题简化并说明一下： 
1． 森林是一个 N行 M列的图。森林的最外一圈以及森林里的某些地方有障碍，Bob 不可能穿过障碍以及后文所提到的食人花； 
2． Bob 初始时位于地图的第 X1 行第 Y1 列，他每次可以往上下左右中的任一方向 移动一格，他的目标是到达出口（地图的第 X2 行 Y2 列）顺利逃生； 
3． 森林中有一种可怕的食人花，它们的嘴始终朝着一个方向，并会吃掉经过它们的嘴朝向的第一个格子中的的一切东西——我们称这个格子被食人花控制——因此，Bob可以从食人花的两侧或后面通过，但如果你控制 Bob经过食人花所控制的格子，呵呵，那就对不起了…… 
4． 管 Bob可以绕过食人花前进， 但很多情况下， Bob还是不得不经过食人花的面前。万幸的是，Bob随身带了K个苹果，他可以把苹果丢在与自己相邻的四个方格中的任一个中；如果苹果丢在了食人花的面前，食人花就会当仁不让地一口吞下——我们知道，所有动植物消化食物都会消耗一段时间——此时 Bob 就可以快速通过正在品尝苹果的食人花了。 
5． 另外，我们规定，食人花并不相互攻击（在所有的游戏中，总是好人打不到好人， 坏人打不到坏人的嘛） ；如果有一个方格被两朵食人花控制， “团结友爱”的食人花会各吃掉半个苹果，因此 Bob 只须扔一个苹果即可通过——前提是此时 Bob 手中必须有苹果。 
6．Bob 的起点和终点一定在空地上，且坐标一定不同。 
现在，给你 Bob 的初始坐标（行、列） ，出口坐标，Bob 携带的苹果个数以及地图，因为 Bob 比较贪吃，所以他希望扔掉的苹果越少越好，现在请你告诉 Bob 需要多少苹果才能顺利逃生（当然，前提是它有足够多的苹果） 。 

第 1行为两个整数 N、M，中间用一个空格隔开，代表森林的行列数； （3<=N，M<=40）  
第 2行有用空格隔开的四个整数 X1，Y1，X2，Y2，分别代表起点和终点的坐标； （起
点与终点是不同的两个点） 
第 3 行有一个整数 K，代表 Bob 随身携带的苹果个数。(0<=K<=100) 
  从第 4 行至第 N+3 行描绘了森林地图，其中“0”代表障碍， “^” 、 “<” 、 “V” 、 “>”分
别代表口朝着上、左、下、右的食人花， “  ”代表空地。 

如果 Bob无法逃出森林，则输出一行“Bob lost his life in the forest.” ；否则，输出至少
需要的苹果数。 

5 8
2 2 4 7
2
00000000
0  <   0
0  < 0 0
0>   0 0
00000000

2