luogu#P3350. [ZJOI2016] 旅行者

[ZJOI2016] 旅行者

题目描述

小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的,也就是有 nn 条从东到西的道路和 mm 条从南到北的道路,这些道路两两相交形成 n×mn\times m 个路口 (i,j)(i,j)(1in,1jm)(1\leq i\leq n,1\leq j\leq m)

她发现不同的道路路况不同,所以通过不同的路口需要不同的时间。通过调查发现,从路口 (i,j)(i,j) 到路口 (i,j+1)(i,j+1) 需要时间 r(i,j)r(i,j) ,从路口 (i,j)(i,j) 到路口 (i+1,j)(i+1,j) 需要时间 c(i,j)c(i,j) 。注意这里的道路是双向的。小 Y 有 qq 个询问,她想知道从路口 (x1,y1)(x1,y1) 到路口 (x2,y2)(x2,y2) 最少需要花多少时间。

输入格式

第一行包含 2 个正整数 n,mn,m 表示城市的大小。

接下来 nn 行,每行包含 m1m-1 个整数,第 ii 行第 jj 个正整数表示从一个路口到另一个路口的时间 r(i,j)r(i,j)

接下来 n1n-1 行,每行包含 mm 个整数,第 ii 行第 jj 个正整数表示从一个路口到另一个路口的时间 c(i,j)c(i,j)

接下来一行,包含一个正整数 qq,表示小 Y 的询问个数。

接下来 qq 行,每行包含 44 个正整数 x1,y1,x2,y2x1,y1,x2,y2,表示两个路口的位置。

输出格式

输出共 qq 行,每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。

2 2
2
3
6 4
2
1 1 2 2
1 2 2 1
6
7

提示

数据规模与约定

  • n×m2×104n\times m \le 2\times 10^4
  • q105q \le 10^5
  • 1r(i,j),c(i,j)1041 \le r(i,j),c(i,j) \le 10^4