Dima and Petya are two friends who have decided to open a café chain named "DimaPetya."
The city where they plan to open their cafés has a rectangular layout, divided by $$$n + 1$$$ streets running west to east and $$$m + 1$$$ avenues running north to south. Each street and avenue spans the entire city without any turns, and no two streets or avenues coincide. The streets are numbered from $$$1$$$ to $$$n + 1$$$ from north to south, while the avenues are numbered from $$$1$$$ to $$$m + 1$$$ from west to east.
To fund their venture, Dima and Petya calculated their earnings and realized they could open exactly two cafés in different city blocks. They plan to study the local customer base before making their decision.
For each of the $$$n \times m$$$ blocks, they determined the number of potential customers residing in each. These customers will not visit a café if it requires crossing more than one street or avenue. If a customer can reach both cafés, they will choose only one.
Dima and Petya seek a placement where both cafés attract at least $$$k$$$ customers.
Your task is to help Dima and Petya compute the number of ways to position their cafés.
The first line of the input file contains three integers: $$$n, m, k$$$ ($$$3 \leq n, m \leq 50$$$, $$$1 \leq k \leq 10^6$$$).
This is followed by $$$n$$$ lines, each containing $$$m$$$ integers that represent the number of potential customers in each block. The $$$i$$$-th line and $$$j$$$-th integer indicate the number of potential customers in the block between streets $$$i$$$ and $$$i + 1$$$ and avenues $$$j$$$ and $$$j + 1$$$. Each block contains at least one and at most $$$100\,000$$$ potential customers.
The output should contain a single integer: the number of ways to select two distinct blocks for the cafés.
4 3 9 2 1 1 1 1 1 1 1 1 3 1 2
32
