小 D 每天都要去上班，小 D 每天从家出发走路去上班，她每秒可以向与她当前所在格子相邻的格子走一步，但城市中有的地方是不允许通行的，城市中有。如果多次经过同一个格子，在计算美丽值之和时该格子的美丽值只被计算一次。
小 D 每天都要去上班。 小 D 所在的城市可以抽象成一个 n+1 n+1 行 m+1 m+1 列的网格，其中行和列均从 0 开始编号。其中小 D 的家位于 (0,0) (0,0)，她要前往 (n,m) (n,m) 上班。 小 D 每天从家出发走路去上班，她每秒可以向与她当前所在格子相邻的格子走一步。但城市中有的地方是不允许通行的，城市中有 nm nm 个障碍，每个障碍形如 (p_i,q_i,x_i,y_i) (p i ,q i ,x i ,y i )，表示不能从 (p_i,q_i) (p i ,q i ) 走到 (x_i,y_i) (x i ,y i )，也不能从 (x_i,y_i) (x i ,y i ) 走到 (p_i,q_i) (p i ,q i )。我们保证不存在 forall ineq j ∀i =j，使得 (p_i,q_i)=(p_j,q_j) (p i ,q i )=(p j ,q j ) 且 (x_i,y_i)=(x_j,y_j) (x i ,y i )=(x j ,y j )。 城市中的很多地方都有美景，因此每个格子有一个美丽值 w w，小 D 希望上班途中经过的格子美丽值之和尽量大，但是她由于睡过头了，上班快要迟到了，她必须在 t t 秒内到达 (n,m) (n,m)。 请你帮她算出，从 (0,0) (0,0) 出发，在 t t 秒内能到达 (n,m) (n,m) 的所有上班路径中经过的格子美丽值之和最大是多少。 如果多次经过同一个格子，在计算美丽值之和时该格子的美丽值只被计算一次。
（图片来源网络，侵删）
