问题描述

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