Count Submatrices with Sum At Most K

Given an \(N \times M\) matrix \(A\), count the number of submatrices (of size at least \(1 \times 1\) and at most \(N \times M\)) whose sum of elements is at most a given integer \(K\).

A submatrix is defined by choosing two rows \(i\) and \(p\) with \(1 \leq i \leq p \leq N\) and two columns \(j\) and \(q\) with \(1 \leq j \leq q \leq M\). The sum of this submatrix can be computed using the formula:

[ S(i,j,p,q) = P(p,q) - P(i-1,q) - P(p,j-1) + P(i-1,j-1), ]

where \(P\) is the prefix sum matrix. Your task is to count all submatrices for which \(S(i,j,p,q) \leq K\).

inputFormat

The first line contains three space-separated integers \(N\), \(M\), and \(K\).

Then \(N\) lines follow, each containing \(M\) space-separated integers representing the matrix \(A\).

outputFormat

Output a single integer, which is the number of submatrices whose sum is at most \(K\).

sample

2 2 4
1 2
3 4

6