Grass for the Goat-dereza

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

A lot of time has passed since the well-known events involving the Goat-dereza. Scared, the Goat ran seven kilometers without stopping, until she suddenly realized she was hungry.

The Goat decided to stop near an \(n \times n\) field divided into unit cells. The cell with coordinates \((1, 1)\) is the top-left cell of the field. Each cell is either full of nutritious and fresh grass, or filled with concrete. In order to get enough to eat and continue running, the Goat needs to visit at least \(k\) cells with grass.

The Goat decided that she will start grazing in some arbitrary cell of the field, and then will always move right or down.

Your task is to calculate the minimum number of cells the Goat needs to pass through in order to visit at least \(k\) cells with grass. If this is impossible, output -1.

Input

The first line contains two natural numbers \(n\) and \(k\) — the dimensions of the field and the minimum number of cells with grass, respectively. The next \(n\) lines describe the field, with \(n\) characters in each line (without spaces). The digit 1 denotes grass, and the digit 0 denotes concrete.

Output

In a single line, output a single integer — the minimum number of cells the Goat must visit to achieve her goal.

Constraints

\(1 \le k \le 50\),

40% of tests: \(1 \le n \le 50\),

60% of tests: \(1 \le n \le 500\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 0101 0001 0100 0001	4

Notes

In the example above, it is optimal for the Goat to visit 4 cells: \((1, 2)\), \((1, 3)\), \((1, 4)\), \((2, 4)\). Along the way, the Goat will eat grass in 3 cells, which is enough to get full.