Description

Charming is a slightly obsessive college student. One day, a bug appears on his phone and the icons on his mobile desktop are out of order. Help Charming arrange the mobile desktop in order!

Specifically, the mobile desktop is a grid of $n \cdot m$, with rows $1,2,\ldots ,n$ from top to bottom, columns $1,2,\ldots ,m$ from left to right. Each icon occupies a grid in the grid diagram.

In order means that all icons are arranged row by row, starting from the first row. That is, for any icon, its position $(i, j)$ in the grid satisfies: $(i - 1) \cdot m + j \leq k$, and $k$ is the number of icons on the desktop.

When an icon moves from $(x_1, y_1)$ to $(x_2, y_2)$, it can be seen as moving $|x_1 - x_2|+|y_1 - y_2|$ distance.

Now Charming wants to know, at least how far does it have to move to put the table in order?

Note: only one icon can be placed in the same square. You can consider that icons can only be moved to the position where there is no icon.

Input

The first line contains three integers $n$, $m$ and $k$ ($1 \leq n, m \leq 500, 0 \leq k \leq n \cdot m$), meaning that Charming's mobile desktop has $n$ rows and $m$ columns with $k$ icons.

Each of the next $n$ lines contains a $01$ string with a length of $m$. If the character in the $i + 1$ line and $j$ column is $1$, it means that there is an icon in the $i$ row and $j$ column of the mobile desktop.

Output

Print an integer, indicating the least distance Charming needs to move to arrange the mobile desktop in order.

Samples

1 1 0
0

0

3 2 1
00
10
00

1

4 4 8
0110
0101
0001
1110

10

Note

In the third test case, you can move like this. It can be shown that $10$ is the least distance to arrange the mobile desktop in order.

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛