众所周知，洛克王国的星辰塔镇守着洛克王国的边陲，而这一次，我们的小洛克lonely_wind在域外与宠物们走散了（实际上是被域外魔物冲散的）。
离开了训练师的宠物们就会变成游离状态，是无法自己移动的，lonely_wind想要与宠物们汇合的话，只能自己去寻找宠物们。
lonely_wind每1秒都可以往上下左右的某一个方向移动一格，当宠物们与lonely_wind汇合时，lonely_wind的攻击力会加上宠物们的攻击力。
现在由于域外魔物的存在，lonely_wind不得不小心翼翼。
lonely_wind如今已是王国的圣魔导师了，如果他和他的宠物们的攻击力大于魔物，则他凭借着强大的实力可以击杀魔物，否则会被魔物吞噬，
离开了训练师的宠物们则处于游离状态，所以会被魔物无视（也就是说魔物并不会攻击还没有和lonely_wind汇合的宠物）。
现在已知魔物每2秒会向四周（上下左右四个方向）扩散一格，同时攻击高的魔物会覆盖攻击低的魔物，
若小洛克和魔物同时到达某一个位置，则只有当到达该位置之前的小洛克的战斗力比魔物大时小洛克才可存活。
除此之外，若小洛克将到达一个已被魔物覆盖的宠物，小洛克必须先战胜那只魔物才能获得宠物。
Input
第一行三个整数，n,m,atk（n,m代表地图大小，地图外为死亡深渊，入者即死,atk为洛克的攻击力）（4≤n,m≤1000）
接下来n行m列的图，‘.’代表空地，‘*’表示魔物，‘#’表示宠物，‘L’为洛克。
接下来一行为魔物的攻击力，以最左上方的魔物为第一个，最右下角的魔物为最后一个，以从左到右，从上到下的顺序给出。
再接下来一行为宠物的攻击力，给出顺序与魔物相同。
其中宠物的数量≤2,魔物的数量≤20，所有攻击值数据在int范围内。
Output
SampleInput1
443..#..L.*.....#*.2317SampleOutput1
6SampleInput2
444...#.L....*.*..#2415SampleOutput2
6Hint
样例1：
第一个魔物的坐标为(2,4)，攻击力为2，第二个魔物的坐标为(4,3)，攻击力为3。
第一个宠物的坐标为(1,3)，攻击力为1，第二个宠物坐标为(4,2)，攻击力为7。
lonely_wind先向上走一格，再向右走一格，拿到第一个宠物，此时他的攻击力增加为4，所以两个魔物都会被lonely_wind给击败。
接下来再向下走3格，向右走1格，拿到第二个宠物，就可以打开传送门了。
lonely_wind总共走了6格，所以答案为6。
让我伤心的是，这题连提交的人都没有。。。其他题目好歹有提交，虽然WA了不少。。。QAQ
接下来由于最多只有两个宠物，我们跑4次bfs就好了，洛克到1号宠物再到2号，洛克到2号再到1号。于是这题就愉快的暴力掉了4000ms+。然后就是考虑优化了。
其实也不需要优化太多，我们可以将所有魔物全部放进队列中一起跑，然后稍微剪个枝就可以过了。我们知道如果一个魔物后抵达A，而它的攻击又弱于或者等于前一个抵达的魔物，那么我们就可以将这个状态给舍弃掉了。1500ms
然后。。。本来是时限2S的，不过牛客上2s的标程要跑太久了。。。所以PC改成1s了。。。。nmd我就估摸着没人过了。。。