小波建房
题号:NC210952
时间限制:C/C++/Rust/Pascal 3秒,其他语言6秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小波是一个优秀的算法竞赛选手,若干年后他走上了人生巅峰。为了报答学校对他的培养,他决定给学校捐一栋实验大楼用于培养像他一样的算法竞赛选手。众所周知我校遍地都是山,想要建设一栋实验大楼需要平整出一片高度一致a*b的矩形空地出来。现在小波想在一块n*m的崎岖山地,为了方便建模我们不妨设每个单位面积的平均高度为,要使下降一单位高度需要花费1的代价,现在小波想知道在n*m的崎岖山地中的平整出一块高度一致的a*b矩形空地的最小花费是多少。

输入描述:

输入第一行包含两个正整数N和M()。接下来N行每行包括M个正整数,表示每个单位面积最 初的平均高度

接下来一行一个数表示有Q组询问。

接下来Q行每行包括两个正整数a_ib_i()。

输出描述:

输出共Q行表示询问的答案。保证答案小于
示例1

输入

复制
3 4
1 8 3 4
5 2 3 1
3 6 2 2
4
1 1
2 2
2 3
3 2

输出

复制
0
4
9
9