题目背景

厂里进来一批板材，每块板材被切成许多小格，每个小格上标着它的单位重量。质检员按客户要求出货：客户给出的限额是 $S$，凡是总重量不超过 $S$ 的矩形板材都能装箱发货。质检员想先知道，这批板材里一共能切出多少种合规的矩形。

题目描述

给定一个 $n$ 行 $m$ 列的整数矩阵 $A$，其中每个元素都是正整数；再给定整数 $S$。

一个子矩形由连续的若干行与连续的若干列确定，即形如第 $r_1$ 行到第 $r_2$ 行、第 $c_1$ 列到第 $c_2$ 列（$1 \le r_1 \le r_2 \le n$，$1 \le c_1 \le c_2 \le m$）的部分，至少含有一个元素。

请求出元素之和不超过 $S$ 的子矩形个数。

输入格式

第一行三个整数 $n, m, S$。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $A$。

输出格式

一行一个整数，表示满足条件的子矩形个数。

输入输出样例 #1

输入 #1

2 2 5
1 2
3 4

输出 #1

6

输入输出样例 #2

输入 #2

1 1 0
5

输出 #2

0

输入输出样例 #3

输入 #3

3 1 10
1
1
1

输出 #3

6

说明

样例解释

样例 1 的矩阵共有 $9$ 个子矩形：四个单格之和依次为 $1,2,3,4$，第一行两格之和为 $3$，第二行两格之和为 $7$，第一列两格之和为 $4$，第二列两格之和为 $6$，整块之和为 $10$。其中不超过 $5$ 的有 $1,2,3,4,3,4$ 共 $6$ 个。

样例 2 中唯一的单格之和为 $5$，超过 $S = 0$，没有合规子矩形。

样例 3 是一列三个格子。子矩形共有 $6$ 个：三个单格之和都是 $1$，两个长度为 $2$ 的区间之和都是 $2$，整列之和为 $3$，全都不超过 $10$。

数据范围

• 对于 $20\%$ 的数据，$n, m \le 20$，$S \le 200$；
• 对于 $50\%$ 的数据，$n, m \le 60$；
• 对于 $100\%$ 的数据，$1 \le n, m \le 500$，$1 \le A_{i,j} \le 10^9$，$0 \le S \le 10^{18}$。

保证答案不超过 $9 \times 10^{18}$。