4118: 「ZJOI2016」旅行者
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小 Y 来到了一个新的城市旅行。她发现了这个城市的布局是网格状的，也就是有 $n$ 条从东到西的道路和 $m$ 条从南到北的道路，这些道路两两相交形成 $n \times m$ 个路口 $(i,j) \ (1 \leq i \leq n,1 \leq j \leq m)$。
她发现不同的道路路况不同，所以通过不同的路口需要不同的时间。通过调查发现，从路口 $(i,j)$ 到路口 $(i,j+1)$ 需要时间 $r(i,j)$，从路口 $(i,j)$ 到路口 $(i+1
,j)$ 需要时间 $c(i,j)$。注意这里的道路是双向的。
小 Y 有 $q$ 个询问，她想知道从路口 $(x_1,y_1)$ 到路口 $(x_2,y_2)$ 最少需要花多少时间。
输入
第一行包含两个正整数 $n,m$，表示城市的大小。
接下来 $n$ 行，每行包含 $m-1$ 个整数，第 $i$ 行第 $j$ 个正整数表示从一个路口到另一个路口的时间 $r(i,j)$。
接下来 $n-1$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个正整数表示从一个路口到另一个路口的时间 $c(i,j)$。
接下来一行，包含一个正整数 $q$，表示小 Y 的询问个数。
接下来 $q$ 行，每行包含四个正整数 $x_1,y_1,x_2,y_2$，表示两个路口的位置。
输出
输出共q行，每行包含一个整数表示从一个路口到另一个路口最少需要花的时间。
样例输入 复制
2 2
2
3
6 4
2
1 1 2 2
1 2 2 1样例输出 复制
6
7提示
数据范围：对于所有的测试数据，$n \times m \leq 2 \times 10^4, \ q \leq 10^5 $，保证相邻路口之间的时间不超过 $10^4$，即 $1≤r(i,j),c(i,j)≤10^4$。