题目描述

给定一个 N × M 的矩阵A，请你统计有多少个子矩阵(最小 1 × 1，最大 N × M) 满足： 子矩阵中所有数的和不超过给定的整数K?

输入格式

第一行包含三个整数N, M 和K. 之后 N 行每行包含 M 个整数，代表矩阵A. 30%的测试数据：1≤N,M≤20； 70%的测试数据：1≤N,M≤100； 100%的测试数据：1≤N,M≤500；0≤Aij≤1000；1≤K≤250000000。

输出格式

一个整数代表答案。

输入样例

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

输出样例

19

数据范围与提示

满足条件的子矩阵一共有19，包含： 大小为1 × 1 的有10 个。 大小为1 × 2 的有3 个。 大小为1 × 3 的有2 个。 大小为1 × 4 的有1 个。 大小为2 × 1 的有3 个。