U538841 邪不压正，刃骨铮铮

## MC模组系列2 #### 骨刃

骨刃是一种类似于飞刀的武器，但与飞刀有所不同。首先，你一开始有$\tt p$把骨刃，然后你每一次只能飞一个骨刃，它会精准地飞向目标，前提是你与目标之间没有任何阻挡。击中目标之后，它会自动飞向最近的目标，而如果周围没有可以抵达的目标，那么这个骨刃会被消耗掉。它击中最近的目标之后，会立即再次寻找下一个目标，但是最多只能击中3个目标，击中3个目标之后，骨刃也会被消耗掉。而每杀死一个目标，你的骨刃便会恢复一个，恢复无上限 它会飞向最近距离目标，而距离则使用平面直角坐标系的距离公式：$\tt (x1,y1)\to(x2,y2)=\sqrt{(x1-x2)^2+(y1-y1)^2}$ 如果有多个距离相等的目标，则优先选择$\tt x$轴大的那个，而如果$\tt x$轴相同，则优先选择$\tt y$轴大的那个 现在，有一个$\tt n \times m$的迷宫，迷宫里有$\tt q$只僵尸，如果飞出一只骨刃需要1秒，骨刃每一段飞行过程也只需要1秒，你的位置是$\tt (x_0,y_0)$，你的移动速度是1格每秒，希望你算出杀死所有僵尸的最短时间，如果无解（骨刃用完回复不了）输出`-1`

第一行，三个整数$\tt n,m,p$，表示迷宫的长和宽，还有骨刃的数量 接下来，输入迷宫，一个$\tt n\times m$的方阵，其中`1`表示墙壁，`0`表示空地 接下来一行，一个整数$\tt q$表示僵尸的数量 接下来$\tt q$行，每行3个整数，第$\tt i$行有$\tt x_i,y_i,b_i$，表示第$\tt i$只僵尸的坐标和血量。 下一行，3个整数$\tt x_0,y_0,a$表示你的所在位置和骨刃的攻击力

一个整数$\tt t$表示最短时间，如果无解，则输出-1

$\tt 1 \le n,m \le 20$ $\tt 1\le q \le 10^6$ 其余都在$\tt int$范围内 [题解](https://www.luogu.com.cn/paste/eilb7wtw)