U597921 [Badcat题目合集]聪明的AC II
题目背景
[[Badcat题目合集]聪明的AC](https://www.luogu.com.cn/problem/U595019) 后续题目。
题目描述
AC在离开了WA的迷宫后，回到了自己的家----要塞，而WA却不死心，心想一定要吃掉AC，于是，WA也来到了要塞里，但是，WA在左上角，因为不熟悉地形迷路了，这时，AC发现教训WA的机会来了，要塞里有N个机关，强度分A、B、C、D四种（从A到D依次递增），WA的体力可以跳过强度小于M的机关（M为字符变量），遇到强度大于K的机关会被杀死（K为字符变量），现在，给出要塞的地图，因为启动机关需要耗费宝贵的能源，AC非常节省，他请你求出在不杀死WA（活捉）的前提下，最少需要启动几个机关。
输入格式
第一行：三个整数，代表N,M和K。
其余15行：一个15*15的矩阵，0代表过道，1代表墙壁，2代表入口（水井），A、B、C、D各代表相应强度的机关。
输出格式
一个整数，代表在不杀死WA（活捉）的前提下，最少需要启动几个机关。