U540538 灵光一霎，威临天下

## MC模组系列 #### 光临之枪

光临之枪是一把极其强大的武器，其攻击带有元素效果，具体而言如下： + 火：攻击敌人后，敌人陷入燃烧，持续$\tt f$秒燃烧伤害，伤害$\tt r$点，但这期间对无法冰冻 + 冰：攻击敌人后，敌人被冰冻，持续$\tt c$秒，这期间若再次受到攻击会击破冰块，造成3倍伤害，并结束冰冻效果 + 雷：攻击敌人后，敌人收到$\tt v$点的额外伤害，敌人陷入一段时间的麻痹，持续$\tt t$秒 元素组合技： + 冰+雷：冰冻敌人后，造成雷击之后这个人所受到麻痹时间也变成原来的3倍，即$\tt 3t$，同时出现一个雷击范围，所有跟那个敌人$\tt u$格曼哈顿距离之内的人都会被麻痹，持续时间为$\tt 2t$ + 雷+火：雷击敌人后，陷入麻痹的过程中，对敌人造成火焰伤害，这段时间火焰伤害会变为原来的两倍，即每秒$\tt 2f$，同时陷入混乱效果。混乱效果指在接下来的$\tt e$，他会每秒对周围$\tt x$格曼哈顿距离的人造成$\tt y$点伤害。当然，这段时间如果混乱的那个敌人死了就不会继续攻击了 光临之枪本身就有的攻击方式： + 元素攻击：将长枪刺向空中，向周围所有没有阻挡的敌人发射同一种元素攻击，初始伤害为$\tt p$，之后元素效果的伤害不算入内。耗时1秒 + 平刺：刺向一个攻击范围内的敌人，攻击范围是$\tt g$格曼哈顿距离，攻击伤害是$\tt k$，耗时1秒 + 蓄力刺：蓄力1秒，连刺3下；蓄力2秒，连刺7下；蓄力3秒，连刺13下。蓄力结束后连刺总耗时总是1秒。每刺一下你可以朝着任意方向移动一格。每一次的攻击范围和攻击伤害同平刺 现在有一个n×m的二维迷宫，有一群僵尸在里面呆着，而你也在里面的$\tt(x0,y0)$处被包围。现在，你手里有一把武士刀，请用这把武士刀杀出重围。请杀完所有僵尸再离开，相信通过这把光临之枪，你必定能以一己之力对抗百万大军 现在，告诉你每只僵尸的状态，正常移动速度1格每秒，现在，请给出杀死所有僵尸的最短时间

第一行，两个数，$\tt n,m$，表示迷宫的长和宽 接下来给出一个$\tt n \times m$的迷宫地图，其中`1`表示墙壁，`0`表示空地。 接下来一个数$\tt q$表示僵尸的数量 接下来$\tt q$行，每一行三个数，分别是$\tt x_i,y_i,b_i$，$\tt (x_i,y_i)$表示第$\tt i$只僵尸的坐标，保证所在位置不为墙壁，$\tt b_i$表示第$\tt i$只僵尸的血量 下面一行，两个整数$\tt f,r$，表示火焰伤害的燃烧时间和伤害 下面一行，一个整数$\tt c$，表示冰冻时间 下面一行，两个整数$\tt v,t$，表示雷电的额外伤害和麻痹持续时间 下面一行，一个整数$\tt u$表示冰+雷的雷击范围 下面一行，三个整数$\tt e,x,y$，表示混乱效果的持续时间、范围和伤害 下面一行，一个整数$\tt p$，表示元素攻击初始伤害 下面一行，两个整数$\tt g,k$ ，表示平刺攻击范围和伤害 最后一行，两个整数$\tt x_0,y_0$表示你的初始坐标

一个数，表示最短时间

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