Problem 5D Genshin Impact

时间限制：2 秒

空间限制：512 MB

故事背景

题目描述

《原神》是由米哈游自主研发的一款全新开放世界冒险游戏。

现在，《原神》推出了全新活动，"大伟哥"将"原石"随机散落在地图上，并设置了一些障碍。

游戏的地图可以被抽象为一个 \(N\times M\) 的矩阵，矩阵中的每个元素是 'x' 或者 'o'，其中 'o' 表示可达的区域，'x' 表示不可达的区域。玩家可以花费 1 秒，从当前区域前往邻近的（上下左右四个方向上距离为 1 的）可达区域。

每天，《原神》中某些区域会出现每日任务，完成每日任务需要一定的时间，完成后可以获得 "原石" 的奖励。

Dr. Xue 是一名资深的原神玩家，但他的时间十分宝贵，每天最多会花费 T 秒在《原神》上。

现在他想知道，若他一开始在地图的 \((x_s, y_s)\) 位置， \(T\) 秒内至多能收集多少 "原石"？

输入格式

第一行四个整数 \(N,M, s_x, s_y, T\)，表示游戏地图的行数、列数、 Dr. Xue 的起始行号、列号以及 Dr.Xue 每天游玩《原神》的秒数。

接下来 \(N\) 行每行 \(M\) 个字符 \(S_{i,j}\)，表示游戏地图。

接下来一行包含一个整数 \(K\), 表示有 \(K\) 个区域有每日任务。

接下来 \(K\) 行每行四个整数 \(x_i, y_i, t_i, r_i\)，表示区域的行号、列号、完成该每日任务需要的秒数、完成每日任务能够获得的奖励。

输出格式

仅一个整数，表示最多可能获得的原石数量。

样例输入1

3 3 1 1 10
ooo
oxo
oxo
3
2 1 2 10
2 3 2 10
3 3 2 1

样例输出1

20

样例1解释

方案如下。

(1, 1) \(\to \) (2, 1) \(\to \) 花费 2 秒进行任务 \(\to\) (1, 1) \(\to \) (1, 2) \(\to\) (1, 3) \(\to \) (2, 3) \(\to \) 花费 2 秒进行任务

总共花费的时间为 9 秒，共完成两个每日任务得到 20 原石。可以证明没有更好的方案。

样例输入2

5 5 3 3 10
ooooo
oxxxx
oxooo
oxxxx
ooooo
4
1 1 2 10
1 5 100 10
5 1 10 5
3 4 10 1

样例输出2

0

样例2解释

前面的区域，以后再来探索吧。

数据范围

对于 \(60\%\) 的数据，\(0\le K\le 1\)

对于所有数据，\(1\le N,M\le 200, 0\le K\le 15, 1\le s_x,x_i\le N, 1\le s_y,y_i\le M, 1\le t_i, r_i\le 10^3, 1\le T\le 86400\)

\(S_{i,j}\) 是 'o' 或者 'x'。起始点 \((s_x,s_y)\) 和每日任务的地点 \((x_i,y_i)\) 对应的字符一定是 o。起始点以及每日任务地点（共 \(K+1\) 个地点）是两两不同的，即每个位置至多只有一个每日任务，且起始点处没有每日任务。