题目描述

给定一个$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

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 \leqslant 20$。

对于$70\%$的评测样例，$N,M \leqslant 100$。

对于$100\%$的评测样例，$1 \leqslant N, M \leqslant 500; 0 \leqslant A_{ij} \leqslant 1000; 1 \leqslant K \leqslant 250000000$。

运行限制

• 最大运行时间：$1s$
• 最大运行内存：$256M$