上班

题号：NC247920
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

小 D 每天都要去上班。

小 D 所在的城市可以抽象成一个 $n+1$ 行 $m+1$ 列的网格，其中行和列均从 $0$ 开始编号。其中小 D 的家位于 $(0,0)$ ，她要前往 $(n,m)$ 上班。

小 D 每天从家出发走路去上班，她每秒可以向与她当前所在格子相邻的格子走一步。但城市中有的地方是不允许通行的，城市中有 $nm$ 个障碍，每个障碍形如 $(p_i,q_i,x_i,y_i)$ ，表示不能从 $(p_i,q_i)$ 走到 $(x_i,y_i)$ ，也不能从 $(x_i,y_i)$ 走到 $(p_i,q_i)$ 。我们保证不存在 $\forall i\neq j$ ，使得 $(p_i,q_i)=(p_j,q_j)$ 且 $(x_i,y_i)=(x_j,y_j)$ 。

城市中的很多地方都有美景，因此每个格子有一个美丽值 $w$ ，小 D 希望上班途中经过的格子美丽值之和尽量大，但是她由于睡过头了，上班快要迟到了，她必须在 $t$ 秒内到达 $(n,m)$ 。

请你帮她算出，从 $(0,0)$ 出发，在 $t$ 秒内能到达 $(n,m)$ 的所有上班路径中经过的格子美丽值之和最大是多少。

如果多次经过同一个格子，在计算美丽值之和时该格子的美丽值只被计算一次。

输入描述:

第一行三个数 ，意义如题面所述。

接下来  行，每行  个数，其中第  行第  列的数表示格子  的美丽值 。

接下来  行，每行四个数 ，表示不能从  走到 ，也不能从  走到 。保证  与  相邻。

数据保证 ，，。

保证小 D 从  出发可以到达每一个格子且一定有一组合法解。

输出描述:

输出一行一个数表示答案。

示例1

输入

复制

输出

复制