Chef and Rectangle Array

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a twodimensional matrix A of dimensions N × M, (N rows and M columns).
He calls the matrix A beautiful if there exist an a×b submatrix, such that all of its elements are equal. In one minute Chef can increase one element of the matrix A by 1. Now he asks you to find out minimum time he will need to make the matrix A beautiful?
Please note that submatrix of a matrix is a continuous rectangular block of the matrix. It can be denoted by two pair of indices (x_{1}, y_{1}) and (x_{2}, y_{2}) where x_{1} ≤ x_{2}, y_{1} ≤ y_{2}. The content of the submatrix will be all the cells (i, j) such that x_{1} ≤ i ≤ x_{2} and y_{1} ≤ j ≤ y_{2}.
Input
 There is a single test case.
 The first line contains two spaceseparated integers N, M denoting the number of rows and columns in the matrix A, respectively
 Each of the next N lines, contains M spaceseparated integers denoting the ith row of the array
 Next line contains one integer Q  amount of questions
 Each of next Q lines contains two spaceseparated integers a and b denoting sizes of submatrix sought.
 All questions are independent and do not influence each other. It means when you answer question, you don't need to change the array
Output
Constraints
 1 ≤ Q ≤ 50
 1 ≤ N, M, A_{i, j} ≤ 1000
 1 ≤ a ≤ N
 1 ≤ b ≤ M
Subtasks
Subtask #1 (13 pts)
 1 ≤ N, M ≤ 50
 TL = 1s
Subtask #2 (35 pts)
 1 ≤ N, M ≤ 200
 TL = 2s
Subtask #3 (52 pts)
 Original constraints
 TL = 4s
Example
Input: 3 4 1 8 3 4 5 2 3 1 3 6 2 2 4 1 1 2 2 2 3 3 2 Output: 0 4 15 9
Explanation
Question #1:
Chef can choose any 1 × 1 submatrix and it will take his 0 minutes to make it beautiful.
Question #2:
The best variant is submatrix
3 1 2 2
Question #3:
The next submatrix Chef can make equal in 15 minutes
5 2 3 3 6 2
Question #4:
3 4 3 1 2 2
Author:  antoniuk1 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/CHSQARR 
Tags  antoniuk1, dynamicprogramming, june16, medium, partialsums 
Date Added:  22072015 
Time Limit:  1  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions