P8783 [Lanqiao Cup 2022 NOI Qualifier B] Counting Submatrices

Given an $N \times M$ matrix $A$, please count how many submatrices (minimum $1 \times 1$, maximum $N \times M$) satisfy that the sum of all numbers in the submatrix does not exceed the given integer $K$.

The first line contains three integers $N$, $M$, and $K$. Then there are $N$ lines, each containing $M$ integers, representing the matrix $A$.

Output one integer representing the answer.

**[Sample Explanation]** There are $19$ submatrices that satisfy the condition, including: There are $10$ of size $1 \times 1$. There are $3$ of size $1 \times 2$. There are $2$ of size $1 \times 3$. There is $1$ of size $1 \times 4$. There are $3$ of size $2 \times 1$. **[Test Case Scale and Constraints]** For $30\%$ of the testdata, $N, M \leq 20$. For $70\%$ of the testdata, $N, M \leq 100$. For $100\%$ of the testdata, $1 \leq N, M \leq 500$, $0 \leq A_{i j} \leq 1000$, $1 \leq K \leq 2.5\times10^8$. Lanqiao Cup 2022 Provincial Contest B Group, Problem F. Translated by ChatGPT 5