统计子矩阵 ### 问题描述 给定一个 $N \times M$ 的矩阵 $A$, 请你统计有多少个子矩阵 (最小 $1 \times 1$, 最大 $N \times M)$ 满足子矩阵中所有数的和不超过给定的整数 $K$ ? ### 输入格式 第一行包含三个整数 $N, M$ 和 $K$. 之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$. ### 输出格式 一个整数代表答案。 ### 样例输入 ``` 3 4 10 1 2 3 4 5 6 7 8 9 10 11 12 ``` ### 样例输出 ```text 19 ``` ### 样例说明 满足条件的子矩阵一共有 19 , 包含: 大小为 $1 \times 1$ 的有 10 个。 大小为 $1 \times 2$ 的有 3 个。 大小为 $1 \times 3$ 的有 2 个。 大小为 $1 \times 4$ 的有 1 个。 大小为 $2 \times 1$ 的有 3 个。 ### 评测用例规模与约定 对于 $30 \\%$ 的数据, $N, M \leq 20$. 对于 $70 \\%$ 的数据, $N, M \leq 100$. 对于 $100 \\%$ 的数据, $1 \leq N, M \leq 500 ; 0 \leq A_{i j} \leq 1000 ; 1 \leq K \leq 250000000$.