 0

# Minimise Sum

Difficulty: HARD Contributed By
Prateek Kalyani
Avg. time to solve
45 min
Success Rate
60%

Problem Statement

#### You are given a matrix of ‘N’ rows and ‘M’ columns and a non-negative integer ‘K’. You have to find the minimum possible sum of all elements in each submatrix after performing most ‘K’ decrements.

##### Note:
``````You can’t decrease a number below 0.
``````
##### For example:
``````You are given ‘K’ = 5, and matrix
‘mat’ = [[1, 2, 3],
[4, 0, 5],
[2 , 7, 4]]
You can do 3 operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.
``````
##### Input Format:
``````The first line of input contains a single integer ‘T’, denoting the number of test cases.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’, representing the rows, columns of the matrix, and the given integer.

The following ‘N’ lines of input contain ‘M’ space-separated integers representing the matrix elements.
``````
##### Output Format:
``````For each test case, print a single integer representing the minimum possible sum of all elements in each submatrix. Print the answer in the modulo 10^9 + 7.

Print a single line for each test case.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N, M <= 500
0 <= K <= 10^12
1<= mat[i][j] <= 10^6

Time Limit: 1 sec
``````
##### Sample Input 1:
``````2
3 3 5
1 2 3
4 0 5
2 7 4
1 2 1
3 4
``````
##### Sample Output 1:
``````246
12
``````
##### Explanation:
``````For the first test case, given K = 5, and matrix
‘mat’ = [[1, 2, 3],
[4, 0, 5],
[2 , 7, 4]]
You can do three operations on element 7 and 2 operations on element 5. Then the sum of all submatrices will be 246.

For the second test case, given K = 1 and the matrix
mat = [[3, 4]]
You can do one operation on element 4. Then the sum of all submatrices will be 12.
``````
##### Sample Input 2:
``````2
2 2 4
1 2
3 4
3 3 3
1 2 3
3 4 5
5 6 7
``````
##### Sample Output 2:
``````24
368
``````   Console