T481966 Shotting Stars & Firefly

夜中月下，静谧林边，稀疏光影，倚照崛崦，成二人影，望空观天，谈星论火，终道之萤火也比流光。 $$——微萤之火，也比流光。$$

二人首见，流星划空，夜色深沉，星光明亮，萤火也耀眼。 二人决定找到林中最亮的地方。 林子是一块 $n\times m$ 的大小矩形，每个地方都有不同的**高度**，高度越高，流星照到那里的光就越亮（高度 $+$ 流星光照值）。 今夜一共会有 $a$ 颗流星从林子上方划过，每颗流星都有自己的亮度 $l$ 和出现的时间 $t$ 以及出现（入场）的位置 $r$ 和方向 $d$ ，流星入场后始终延 $d$ 直线前进，直至离开林子（光照范围在离开后失效），在有流星的格子周围 $p$ 格会获得 $l-p$ 的亮度（直至 $l-p=0$）。 同时会有 $b$ 只飞萤出现林中，每只飞萤都有自己的亮度 $l$ 和位置 $x$ 和 $y$。飞萤的亮度不会扩散至周边位置。当飞萤所在位置受流星光照（重合也算）时，飞萤就只有原本一半的光亮（向下取整）。 问今夜何时何地最亮（若有多解则输出最小解）。

输入正整数 $n$，$m$。 接下来输入 $n\times m$ 的整数矩形，表示地形高度。 输入正整数 $a$ 表示流星个数。 接下来输入亮度 $l$，时间 $t$，和位置（正整数 $r$ 和字符串 $d$）表示从林子的 $d$ 边缘从上往下（从左往右）数第 $r$ 个格子出现（并开始发光）。 输入正整数 $b$ 表示飞萤个数。 接下来输入亮度 $l$，和位置 $x$，$y$。

输出最亮的时间 $t$ 和位置 $x$，$y$。

出题人：[sakura_10](https://www.luogu.com.cn/user/757524)， [gaoyangyang](https://www.luogu.com.cn/user/733470) $1 \le n, m \le 20$ $r \le n$ **or** $r \le m$ $0\le a \le 10$ $0\le b\le m \times n$ $d$ 仅为 $\operatorname{top}$，$\operatorname{left}$，$\operatorname{right}$，$\operatorname{bottom}$ 中其一 $t$ 初始值从 $0$ 开始 std 代码各测试点用时均在 $0.5$ 秒以内，保证时间充足。 ## 样例提示： #### 对于样例一 没有流星，只有飞萤，输出 $0$ 和受飞萤影响亮度最大的位置即可。 #### 对于样例二 没有流星，没有飞萤，输出 $0$，$0$，$0$。 #### 对于样例三 共有三颗流星， 分别从顶边缘（$x=1$）$y=3$ 的位置从 $1$ 时刻向下移动，从左边缘（$y=1$）$x=2$ 的位置从 $1$ 时刻向右移动，从右边缘（$y=4$）$x=2$ 的位置从 $2$ 时刻向左移动。 易得出当 $3$ 时刻时，（$2$，$3$）的亮度为 $2$（高度）$+ 1 + 4 + 3$（流星）$=10$，亮度最大，故输出 $3$，$2$，$3$。