eolymp
bolt
Try our new interface for solving problems
Problems

Islands

Islands

Time limit 0.3 seconds
Memory limit 64 MiB

The government of the Olimpiya plans to build few islands for bringing there tourists becausae it don't want to fall behind of the modern world tendency. The map of islands is already prepared and shows by itself a table with the sizes N x of M cells. Every cell can be water or land. A set of cells which present land is an island, when it is possible to get in any other from any of them moving nearby for horizontal lines or vertical lines cells, and there are no other such cells out of the set.

It was decided for a comfort to build bridges between some islands so that all of islands became united between itself. Bridges must be built only by vertical lines or horizontal lines and pass only on cells with water; must begin and end in cells with land. It is possible to count the quantity of cells of water which it passes through as a cost of building of the bridge. You have to find the minimum possible total worth of building of the group of bridges which would be connected all of islands between there. In other words, that it have to be possible to get from every cell of land to other; you are moving to nearby on a vertical line and horizontal line of cells of land or by the bridges. Two different bridges can intersect between itself, that to pass through the same cell of water on different levels.

The Task

You have to write the program ISLANDS, that after the map of islands will find the minimum cost of building of the group of bridges which connect all of islands.

Input data

There are two integers N and M (1 ≤ N, M500) - sizes of the map of islands in the first line of input-file. Each of the next N lines has M symbols 0 (water) or 1 (land).

Outpur

Print one integer - the minimum cost of the building of bridges in the one line of output-file. If it is not impossible to connect island by bridges you have to write a number -1.

Examples

Input example #1
5 5
01110
00100
10010
00100
10001
Output example #1
8
Author Shamil Yagiyaev
Source 2008 XXI All-Ukrainian Informatics Olympiad, Lvov, April 5 - 11, Round 1