U545139 星夜之昏，唯我独尊

## MC模组系列5 #### 星杖

星杖是一款强力武器，攻击方式如下： + 影星飞跃：发射一道光波，朝前后左右任意方向，造成$\tt y$点伤害，消耗1秒 + 群星陨落：举高法杖，每蓄力$\tt u$秒过后对周围$\tt u$格曼哈顿距离的敌人召唤流星砸下，$\tt u$不是一个定值，可以自己选择，流星砸中每一个敌人都会对周围$\tt v$格曼哈顿距离的人造成$\tt w$点伤害，每一个敌人可能会被多次伤害。蓄力结束后攻击完成需要一定时间，时间的长度等于受到伤害的敌人的数量 + 时空裂隙：在距离原地$\tt k$格曼哈顿距离内的地方召唤一个分身，之后$\tt d$秒，分身会在他所在位置重复所有本体的攻击，第$\tt d$秒时分身消失。召唤分身需要3秒 + 星移斗转：在地图上任意位置召唤一个法阵，将召唤点位所有距离在$\tt b$格之内的敌人传送到你指定的位置，耗时4秒 + 唯我独尊：在上述几种攻击方式全部出过至少一遍之后才可以使用这个攻击。这个攻击可以瞬间秒杀所有在你$\tt g$格曼哈顿距离范围内的敌人，并且时间此时暂停，有$\tt h$秒的时间你的攻击所消耗的时间不计入总时间 现在有一个$\tt n \times m$的二维迷宫，有一群僵尸在里面呆着，而你也在里面的$\tt (x_0,y_0)$处被包围。现在，你手里有一把星杖，请用这把法杖杀出重围。请杀完所有僵尸再离开，你的移速每秒1格，相信通过这把法杖，你必定能以一己之力对抗百万大军

第一行，两个整数$\tt n,m$表示迷宫的长和宽 接下来读入迷宫，一个$\tt n \times m$的方阵，每一格一个数字`1`表示墙壁，`0`表示空地 下面一行，一个整数$\tt q$表示僵尸的数量 接下来3行，每行3个整数，$\tt x_i,y_i,b_i$，其中$\tt (x_i,y_i)$是第$\tt i$只僵尸的坐标，$\tt b_i$是第i只僵尸的血量 下面一行，一个整数$\tt y$表示影星飞跃的攻击伤害 下面一行，两个整数$\tt v,w$表示群星陨落的流星落地时每一个流星的攻击范围和攻击伤害 下面一行，两个整数$\tt k,d$表示时空裂隙的分身召唤范围和持续时间 下面一行，一个整数$\tt b$表示星移斗转的法阵范围 下面一行，两个整数$\tt g,h$表示唯我独尊的攻击范围和时间暂停的时间 最后一行，两个整数$\tt x_0,y_0$表示你的初始位置

一个整数，表示杀出迷宫的最短时间

$\tt 1 \le n,m \le 20$ $\tt 1 \le q \le 10^6$ [题解](https://www.luogu.com.cn/paste/oj8yb5ni)