2009 Mock DWITE by A.J.: Problem 5
Every day, Brenda is faced with the monumental task of getting to work
by car. Brenda lives in a city containing north-south roads and
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
Avenue, the next westernmost
Avenue, and so on; the northernmost east-west road is called
Street, the next northernmost
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 minutes to
move between two adjacent intersections, where
is constant.
Each intersection has a traffic light. The traffic light at the
intersection of Street and
Avenue
spends
minutes green in the north-south direction, then
immediately switches to being red for
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 Specification
There will be five cases given one after another in the input.
The first line of each case contains three space-separated integers:
,
, and
, as described
above.
The next line contains two space-separated integers: and
, indicating that Brenda's home
is located at
Street and
Avenue.
The next line contains two space-separated integers: and
, indicating that Brenda's place
of work is located at
Street and
Avenue.
A block of lines follows, each containing
space-separated
integers. The
integer in the
line in
this block gives
.
A block of lines follows, each containing
space-separated
integers. The
integer in the
line in
this block gives
.
Output Specification
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.
Comments