题目描述

移动平台在风险地图上导航时，进入每个格子都会产生基础代价和风险代价。给出地图、基础代价矩阵、风险矩阵、风险权重和预算，请计算从起点到终点的最小代价。

从一个格子移动到相邻四方向格子时，新增代价为目标格子的 base + risk_w * risk。起点自身不产生代价。若多条路径总代价相同，选择步数更少的路径。

输入格式

第一行输入地图尺寸 H W。

第二行输入 risk_w budget。

接下来 H 行输入地图，. 表示可通行，# 表示障碍。

接下来 H 行，每行 W 个数，表示基础代价矩阵 base。

接下来 H 行，每行 W 个数，表示风险矩阵 risk。

最后一行输入 sr sc tr tc，表示起点和终点的 1-based 行列坐标。

输出格式

若终点不可达，输出 UNREACHABLE。

若可达且最小代价不超过预算，输出：

EXECUTABLE cost steps

若可达但超过预算，输出：

OVER_BUDGET cost steps

其中 cost 保留 6 位小数。

判定规则

使用标准输出比较。路径只允许四方向移动。起点若不是障碍则初始代价为 0；终点最小代价与预算比较包含边界。

数据范围与测试提示

• 正式测试会覆盖样例没有出现的边界输入，请不要依赖样例规模或样例顺序写特判。
• 输出只包含题目要求的字段，不要输出调试信息；浮点结果按题面要求保留 6 位小数。
• 风险地图可能包含障碍、起点等于终点、预算刚好用尽等极限情况。
• 只允许四方向移动；终点最小代价与预算比较包含边界，代价相同时按题面规则稳定选择。
• 起点代价为 0，不计入起点格代价；终点代价等于预算仍输出可执行。

样例

输入样例 1

2 3
2 10
...
...
1 1 1
1 1 1
0 1 0
0 2 0
1 1 2 3

输出样例 1

EXECUTABLE 5.000000 3

输入样例 2

2 2
1 10
.#
#.
1 1
1 1
0 0
0 0
1 1 2 2

输出样例 2

UNREACHABLE