Apricot Harvest

Interview

Time limit2sMemory limit1024 MB

Summary

Count all square sub-tables of the n by m grid whose sum is less than S, over every square size.

Level: Easy3 of 10
Topics: Prefix sum, Brute force
Solved: No attempts yet

Statement

An $n \times m$ table is filled with numbers. The king set a value $S$ , and every $k \times k$ square on the field must have a harvest of at least $S$ . A square may consist of a single tree. King Briko I doubted the agronomists' report and asked for the number of squares that fail this criterion, that is, squares whose sum is less than $S$ .

Input

The first line contains three integers $n$ , $m$ , $S$ : the dimensions of the experimental apricot field and the value set by the king. Next come $n$ lines with $m$ numbers each, where $a_{ij}$ is the number of apricots on the tree in row $i$ , column $j$ ( $1 \le n, m \le 30$ ; $0 \le S \le 10^{9}$ ; $0 \le a_{ij} \le 10^{7}$ ).

Output

Print a single number: the count of squares where the harvest criterion is not met.

Examples2

Example 1
Input
```
2 3 4
1 2 3
4 5 6
```
Expected output
```
3
```
Example 2
Input
```
2 3 11
1 2 3
4 5 6
```
Expected output
```
6
```