A24219.神庙大冒险

时间限制:1000ms
空间限制:128mb

Yuilice掉入了一个奇怪的神庙，在这个神庙当中充斥着各种各样的怪物，Yuilice原本还挺怕的，但是看下时间马上要到四点给B班上课了，因此他一下子精神了，准备火速回到柯桥上课。

我们可以把神庙看成是一个$N \times N$的二维矩阵，Yuilice一开始存在着$T$点体力值，他只能进行向右或者向下的移动，并且从行为$S_x$，列为$S_y$的起点出发。在这个矩阵当中，存在着以下几种情况

• 字符.代表道路，Yuilice每走一格道路就会损失1点体力值。
• 字符M代表怪物，Yuilice因为迫切的想要回到B班上课，因此他可以使用$k$点体力消灭该格的怪物来到该格当中。(假如起点就有怪物，那么怪物就会被Yuilice降落的余波消灭，不需要消耗体力值)
• 字符D代表神奇果实，Yuilice可以来到该格吃下果实，补充$z$点体力，并且每格的果实只能被食用一次。

现在已知终点所处坐标为$[N,N]$请你计算出Yuilice回到B班时，他最多还有多少体力值来给B班的同学上课呢？

第一行包括六个整数$n,T,k,z,S_x,S_y$，分别代表地图的大小、初始体力值、消灭怪物的体力值、补充体力值、与起点横坐标与纵坐标。

随后$n$行，每行输入$n$个字符，代表神庙的地图。

输出一个整数代表Yuilice到达B班的最多体力值。

【样例解释】

第一组样例:

• Yuilice由$[1,1]$来到$[2,1]$ 体力值为:2
• Yuilice由$[2,1]$来到$[3,1]$吃下了神奇果实 体力值为:102
• Yuilice由$[3,1]$来到$[3,2]$消灭了怪物 体力值为:101
• Yuilice由$[3,2]$来到$[3,3]$ 体力值为:100

第二组样例:

• Yuilice从落地开始最多走4步到达终点，总计吃5个果实，最后体力值为503

第三组样例:

• 无论Yuilice如何行走，都要消灭4只怪物，体力值变化为。

• $[1,1] , T = 3$

• $[1,2] , T = 3 - z = 2$

• $[1,3] , T = 2 - z = 1$

• $[2,3] , T = 3 - z = 0$

• $[3,3] , T = 3 - z = -1$

• 最终体力透支为-1

注: 该路线只是多条相同数值的路线的其中一条。

【数据限制】

对于$50\%$的数据$1 \leq n \leq 15 , 1 \leq T,k,z \leq 10^9 , 1 \leq S_x,S_y \leq n$。

对于$100\%$的数据$1 \leq n \leq 100 , 1 \leq T,k,z \leq 10^9 , 1 \leq S_x,S_y \leq n$。

题目保证$[S_x,S_y] \neq [N,N]$