3794: 宝石加工(第三轮04)
题目描述
在流水线最后，有两条传送带和一个加工机器。两条传送带会送来两串宝石原料， 在每一时 刻，工作人员可以决定是变卖传送带 1 最前面的原料（会获得一定的利润），还是变卖传送 带 2 最前面的原料（同理），又或者是将两传送带最前面的原料加工成一个成品宝石，并且 出售掉获得利润。
这位聪明的老板发现了一种奇妙的价值鉴定方法。具体的， 如果把一个价值为 a 的宝石原 料和一个价值为 b 的宝石原料进行加工，会得到一个售卖价格为 a + b 元的宝石。
现在有两列宝石原料， 长度分别为 n, m ，价值分别为 Ai 和 Bi， 如果直接变卖， 获利分别 是 Di 和 Ei，按顺序排成一排。
老板又苦恼地发现，两个宝石进行加工所需的成本无法简单确定，只好一对一对地估量成本。 具体地，如果将第一列第 i 个宝石原料与第二列第 j 个宝石原料进行加工，需要花费 ci,j 元。老板把这一切告诉了小明和小红。
现在老板出题了： 作为盈利工厂， 工厂显然是希望获得最大利润的。如果我现在选定 l1, r1, l2, r2，并将第一列编号在 [l1, r1] 区间内的宝石原料按照编号从小到大的顺序，从前到 后放在传送带 1 上，将第二列编号在 [l2, r2] 区间内的宝石原料同理放在传送带 2 上，执 行加工流程，工厂最多能获利（售卖总价-加工总成本）多少元？
并且老板脑子太好使了，直接问了小明二人 q 个问题，你能帮帮他们吗？
注意，本题编号从 1 开始，并且宝石原料不能与空气合成。 文件样例： ex_produce.zip
输入
第一行三个正整数 n, m, q，表示第一列宝石原料个数、第二列宝石原料个数以及老板问题 的个数。
第二行 n 个正整数 Ai，表示第一列宝石原料价值。
第三行 m 个正整数 Bi，表示第二列宝石原料价值。
第四行 n 个正整数 Di，表示第一列宝石原料变卖获利。
第五行 m 个正整数 Ei，表示第二列宝石原料变卖获利。 之后的 n 行，第 i 行 m 个正整数 ci,j，表示加工成本。 之后的 q 行，每行四个正整数 l1, r1, l2, r2，代表一个问题。
输出
共 q 行，每行一个正整数，表示最大盈利。
样例输入 复制
3 2 2
2 2 2
3 2
1 2 1
1 0
1 1
2 1
0 1
1 3 1 2
2 2 2 2样例输出 复制
9
3提示
【样例 1 输入】
3 2 2
2 2 2
3 2
1 2 1
1 0
1 1
2 1
0 1
1 3 1 2
2 2 2 2
【样例 1 输出】
9
3
【样例 2 输入】
5 6 10
15 19 20 21 15
11 9 8 18 19 13
27 24 22 19 11
24 10 16 21 11 19
2 6 6 8 1 10
13 13 9 14 12 15
12 9 13 12 11 4
3 11 14 5 9 13
12 8 1 15 15 9
4 4 2 2
1 5 1 2
1 3 4 5
3 5 5 6
1 4 1 1
4 4 2 6
1 3 4 5
2 3 1 4
3 4 2 2
4 5 3 5
【样例 2 输出】
29
137
105
83
116
97
105
117
51
79
【备注】
对于 20% 的数据， n × m ≤ 103, q ≤ 10^3 。 对于另 20% 的数据， n = 1。
对于另 32% 的数据， l1 = 1, r1 = n。
对于 100% 的数据， 1 ≤ n × m ≤ 5 × 10^4, 1 ≤ q ≤ 10^5, 0 ≤ Ai, Bi, ci,j, Di, Ei ≤ 109, 1 ≤ l1 ≤ r1 ≤ n, 1 ≤ l2 ≤ r2 ≤ m。