Every morning you have to drive to your workplace. Unfortunately, roads are under constant repair. Fortunately, administration is aware that this may cause trouble and they enforce a strict rule on roadblocks: roads must be blocked only half of the time. However, contractors are free to schedule their working hours, still they must follow regulations: • Working periods (when the road is blocked) and rest periods (when the road is open) must alternate and be of fixed length. • The beginning of the day (time zero) must coincide with the beginning of a period. Write a program that, given a description of the road network and of contractors schedules outputs the minimal time needed to drive from home to work. Input Input consists of several test cases, each of them following the description below. A blank line separates two consecutive cases. The road network is represented on a N × N grid and the first line of the input consists in the number N, 2 ≤ N ≤ 50. Then, come N lines of N characters that represent the road network at time zero. Those lines are made of ‘.’ (standing for open road) and ‘’ (standing for roadblock) and they encode the rows of the grid in increasing order, while columns are also presented in increasing order. Conventionally, your home is at the position first row, first column, while your workplace is at the position last row, last column. Furthermore, you leave home at time t = 0, that is, your starting position is first row, first column at time zero. At a given time t, your car must be on some “open road” cell. It takes one unit of time to drive to any of the four adjacent cells heading toward north, south, west or east, and you may also choose to stay on the same cell for one unit of time. Of course, those five moves are valid if and only if the targeted cell exists and is free at time t + 1. Finally, come N lines of N characters that represent the contractors schedules. Those lines match the ones of the grid description and are made of N characters ‘0, 1, ..., 9’ that specify the duration of the working (and rest) period for a given cell. Observe that ‘0’ is a bit special, since it means that the corresponding cell status does not change. Output For each input case, the output consists in a single line, holding either the requested time, or ‘NO’, if driving from home to work is not possible. The outputs of two consecutive cases will be separated by a blank line. Sample Input 10 .******** ........** ..* ..*
2/2 ..* ........ ..* .*****.* ........ ********.. 0000000000 0000000000 0000000000 0000000000 0000000000 0123456780 0000000000 0000000000 0123456780 0000000000 3 ... **. **. 021 002 000 Sample output 34 NO