Minimum Moves

Go from the top-left corner to the bottom-right corner. Each step moves 1..k cells along one axis, and every cell passed through must be empty, including the start and landing cells. Return −1 if the target is unreachable.

输入格式

The first line contains n m k, followed by n lines of m values that are 0/1. The original full domain 1≤n,m,k≤100 is kept. This site specifies: if either endpoint is an obstacle, return −1, including a 1×1 obstacle grid; an empty 1×1 grid gives 0.

输出格式

Output a single integer answer.

样例 1

输入：

2 2 2
0 0
1 0

输出：

2

样例 2

输入：

2 3 5
0 0 0
1 0 0

输出：

2

样例 3

输入：

1 1 1
1

输出：

-1

样例说明

The outputs of the three public examples are, in order: 2; 2; -1. Verified by independent enumeration or direct simulation.