该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Background

Muxue the youth is studying matrix coloring magic. He can use k×k magic squares to color matrix regions black. Now he wants to know whether the target matrix can be obtained by overlaying several k×k black submatrices.

Problem Description

Muxue has an n×m matrix, initially all white. In each operation, Muxue can choose a k×k submatrix (k is given) and color it black.

Note: The same cell can be colored multiple times, but only the last coloring determines the final color.

Now given a target matrix, Muxue wants to know whether it can be obtained through several operations as described above. If yes, output a feasible number of operations (not necessarily minimal); otherwise output -1.

Input Format

First line: three integers n, m, k (1 ≤ k ≤ n, m ≤ 1000)
Next n lines: each line contains a 01 string of length m, representing the target matrix (0 means white, 1 means black)

Output Format

If achievable, output a feasible number of operations; otherwise output -1.

Sample Input and Output #1

Input #1

3 3 2
111
111
111

Output #1

4

Explanation/Notes

Explanation for Sample 1: Four 2×2 submatrices can cover the entire 3×3 matrix.

This problem uses Subtask bundled testing