Traffic Light Navigation

In this problem, you are given an (n \times m) grid representing intersections controlled by traffic lights. Each intersection has two associated numbers: the first ((h)) represents the configuration for horizontal movement and the second ((T)) represents the cycle period of the light. For moving right into an intersection, the traffic light is green if: [ \text{if } h = 0: \quad (t \bmod T) < \left\lfloor\frac{T}{2}\right\rfloor, \quad \text{and if } h = 1: \quad (t \bmod T) \ge \left\lfloor\frac{T}{2}\right\rfloor. ] Similarly, for moving down, the decision is based on the vertical light which is given by the second number in the pair. (In our input the vertical configuration is provided as the second integer of each pair and the same rule applies: if the value is 0 then the light is green in the first half of the cycle, and if the value is 1 then it is green in the latter half.)

A car starts at the top‐left intersection (i.e. position (1, 1)) at time 0. Each move (either right or down) takes exactly 1 second. When moving right, you may only enter the destination intersection if its horizontal light is green at the time of arrival; when moving down, you may only enter if its vertical light is green. Your task is to determine the earliest time the car can reach the bottom‐right intersection (position (n, m)). If it is impossible to reach the destination under the given conditions, output -1.

Note: In all test cases, the cycle period (T) is 1. Under these conditions, notice that for any intersection with a configuration value of 0, the corresponding direction will never be green; and for those with a configuration value of 1, the light will be green at every integer time (since (t \bmod 1 = 0) and (0 \geq 0)).

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains two integers (n) and (m) separated by a space, denoting the number of rows and columns respectively.

This is followed by (n) lines, each containing (2 \times m) integers. Each line describes a row of intersections. For each intersection, there are two integers: the first represents the horizontal traffic light configuration (h) (either 0 or 1) and the second represents the cycle period (T) (which will be 1 in all test cases).

For example, a row might look like:

0 1 1 1 0 1

which corresponds to three intersections with configurations: (0,1), (1,1), (0,1).

outputFormat

Output a single integer on standard output (stdout) — the earliest time (in seconds) at which the car can reach the bottom-right intersection. If it is impossible to reach the destination, output -1.## sample

3 3
0 1 1 1 0 1
1 1 0 1 1 1
0 1 1 1 0 1

4