### 2009 Mock DWITE by A.J.: Problem 5

## Traffic Lights

Every day, Brenda is faced with the monumental task of getting to work by car. Brenda
lives in a city containing *C* north-south roads and *R* east-west roads.
Every north-south road intersects every east-west road exactly once. All north-south
roads are parallel to each other and perpendicular to all east-west roads (which
are themselves all mutually parallel as well). Conveniently, the westernmost north-south
road is called 1^{st} Avenue, the next westernmost 2^{nd} Avenue, and
so on; the northernmost east-west road is called 1^{st} Street, the next
northermost 2^{nd} Street, and so on.

Two intersections are considered
adjacent if it is possible to move from one intersection to another along a road
without passing through any other intersection on the way. It takes Brenda exactly *X*
minutes to move between two adjacent intersections, where *X* is constant.

Each intersection has a traffic light. The traffic light at the intersection of
*i*^{th} Street and *j*^{th} Avenue spends
*g*_{ij} minutes green in the north-south direction, then immediately switches
to being red for *r*_{ij} in the north-south direction, then repeats this
cycle indefinitely. The color in the
east-west direction is always opposite to the color in the north-south direction at any
instant in time.
Brenda cannot leave an intersection unless the light is green in the
direction of travel *at the time of departure from that intersection*.

Brenda's
apartment is at one intersection, and her place of work is at another intersection.
Brenda departs from her home at time zero, cannot leave the city, and obviously must
travel along the roads. She knows that, at her time of departure, all lights in the
city have *just* switched to green in the north-south direction.
Help her determine the earliest time at which she can possibly arrive at work.

### Input

There will be five cases given one after another in the input.The first line of each case contains three space-separated integers:

*R*,

*C*(1 ≤

*R*,

*C*≤ 40), and

*X*(1 ≤

*X*≤ 5), as described above.

The next line contains two space-separated integers:

*R*

_{h}and

*C*

_{h}(1 ≤

*R*

_{h}≤

*R*, 1 ≤

*C*

_{h}≤

*C*), indicating that Brenda's home is located at

*R*

_{h}

^{th}Street and

*C*

_{h}

^{th}Avenue.

The next line contains two space-separated integers:

*R*

_{w}and

*C*

_{w}(1 ≤

*R*

_{w}≤

*R*, 1 ≤

*C*

_{w}≤

*C*), indicating that Brenda's place of work is located at

*R*

_{w}

^{th}Street and

*C*

_{w}

^{th}Avenue.

A block of

*R*lines follows, each containing

*C*space-separated integers. The

*j*

^{th}integer in the

*i*

^{th}line in this block gives

*g*

_{ij}(1 ≤

*g*

_{ij}≤ 5).

A block of

*R*lines follows, each containing

*C*space-separated integers. The

*j*

^{th}integer in the

*i*

^{th}line in this block gives

*r*

_{ij}(1 ≤

*r*

_{ij}≤ 5).

### Output

For each case given in input, in the order given, output one line containing one integer: the minimum amount of time, in seconds, it takes for Brenda to get to work.### Sample Input (only two cases shown)

1 2 1 1 2 1 2 2 3 4 2 2 2 3 2 1 2 2 5 3 5 4 1 5 2 5

### Sample Output

0 8

### Explanation

In the first case, Brenda's home and place of work are on the same intersection, so we assume that it takes no time at all for her to move from one to the other.In the second case, Brenda waits for five minutes for the light at her initial intersection to turn green in the east-west direction, and three minutes for her to travel east one block. That totals eight minutes.

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Sep 26, 2009

**Author:** bbi5291

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...