Woburn Challenge 2018-19 Round 1 - Senior Division

It's time for a history test! Unfortunately, while some students have come well-prepared, others appear to have forgotten about the test entirely. They may need some "inspiration" to get through it with passing grades.

The desks in H.S. High School's history classroom are laid out in a nice, traditional grid. The grid has $R$ $(1\le R\le 50000)$ rows, numbered $1\dots R$ from front to back, and $C$ $(1\le C\le 10)$ columns, numbered $1\dots C$ from left to right. The state of each desk in a given row $r$ and column $c$ is described by an integer $D_{r,c}$ $(0\le D_{r,c}\le 2)$, which is one of the following:

• 0: That desk is unoccupied
• 1: That desk is occupied by a "type-1" student — one who has studied for the test
• 2: That desk is occupied by a "type-2" student — one who has not studied for the test

Each type-2 student is in trouble… unless they can catch a glimpse of inspiration, in the form of a type-1 student's test paper. Without looking too suspicious, a student can see manage to see the papers on some desks directly in front of them, in the same column. However, they can only clearly see at most the closest $K$ $(1\le K\le R-1)$ desks in front of them. In other words, the test paper of a type-1 student sitting in row $r_1$ and column $c_1$ can be seen by a type-2 student sitting in row $r_2$ and column $c_2$ if and only if $c_1=c_2$ and $r_2-K\le r_1\le r_2-1$. Note that a type-2 student doesn't gain any additional benefit from seeing multiple type-1 students' papers, and that it's possible for a single type-1 student's paper to inspire multiple type-2 students.

How many of the type-2 students can be inspired by looking at at least one type-1 student's test paper?

Subtasks

In test cases worth 4/13 of the points, $K\le 10$.
In test cases worth another 5/13 of the points, $K=R-1$.

Input Specification

The first line of input consists of three space-separated integers, $R$, $C$, and $K$.
$R$ lines follow, the $i$-th of which consists of integers, $D_{i,1\dots C}$, for $i=1\dots R$.

Output Specification

Output a single integer, the number of type-2 students who can be inspired.

Sample Input

5 3 2
1 0 1
1 2 2
0 1 2
2 1 2
0 2 2

Sample Output

4

Sample Explanation

The type-2 students in the 2nd and 3rd rows of the 3rd column can both be inspired by the type-1 student sitting at the front of that row.

The type-2 student in the 4th row of the 1st column can be inspired by the type-1 student sitting 2 desks in front of them.

Finally, the type-2 student at the back of the 2nd column can be inspired by either of the type-1 students sitting 1 or 2 desks in front of them.