Even though it is June, the city of SnowVille is facing some serious trouble: last night, lots of snow covered all the roads in the city.
The road network looks as follows: There are N important places in the city. The places are labeled 0 through N-1. Each road in the city connects two of these places. Each pair of places is connected by at most one road. Each road can contain one or more car lanes. Each road is bidirectional and the number of lanes is the same for both directions.
Sadly, all the snow plows except for one were already decommissioned for the summer.
The one snow plow that is still available is in a depot at place 0.
Whenever the snow plow drives along a road, it is able to clean a single lane going in the direction in which it travels.
Hence if you want to clean an entire road with K lanes going in each direction, the snow plow must drive along this road at least K times in each direction.
You are given a String roads that describes the road network:
If there is no road between places i and j, character j of element i of roads is '0'.
The maximum number of lanes a road can have in each direction is 9.
If there is a road with k lanes in each direction, character j of element i of roads is 'k' (that is, '1' if there is one lane, '2' if there are two lanes, etc.)
Traversing a single lane of any single road takes the snow plow exactly one minute. Return the least number of minutes in which the snow plow can clean all lanes on all roads.
If cleaning all lanes on all roads is impossible, return -1 instead.