Problem 2: Siruseri Metro System,
*(K Narayan Kumar, CMI)*

The city of Siruseri is impeccably planned. The city is divided
into a rectangular array of cells with *M* rows and
*N* columns. Each cell has a metro station. There is one
train running left to right and back along each row, and one
running top to bottom and back along each column. Each trains
starts at some time *T* and goes back and forth along its
route (a row or a column) forever.

Ordinary trains take two units of time to go from one station to the next. There are some fast trains that take only one unit of time to go from one station to the next. Finally, there are some slow trains that take three units of time to go from one station the next. You may assume that the halting time at any station is negligible.

Here is a description of a metro system with 3 rows and 4 columns:

S(1) F(2) O(2) F(4) F(3) . . . . S(2) . . . . O(2) . . . .

The label at the beginning of each row/column indicates the type
of train (`F` for fast, `O` for ordinary, `S`
for slow) and its starting time. Thus, the train that travels along
row 1 is a fast train and it starts at time 3. It starts at station
(1,1) and moves right, visiting the stations along this row at
times 3, 4, 5 and 6 respectively. It then returns back visiting the
stations from right to left at times 6, 7, 8 and 9. It again moves
right now visiting the stations at times 9, 10, 11 and 12, and so
on. Similarly, the train along column 3 is an ordinary train
starting at time 2. So, starting at the station (3,1), it visits
the three stations on column 3 at times 2, 4 and 6, returns back to
the top of the column visiting them at times 6,8 and 10, and so
on.

Given a starting station, the starting time and a destination station, your task is to determine the earliest time at which one can reach the destination using these trains.

For example suppose we start at station (2,3) at time 8 and our aim is to reach the station (1,1). We may take the slow train of the second row at time 8 and reach (2,4) at time 11. It so happens that at time 11, the fast train on column 4 is at (2,4) travelling upwards, so we can take this fast train and reach (1,4) at time 12. Once again we are lucky and at time 12 the fast train on row 1 is at (1,4), so we can take this fast train and reach (1,1) at time 15. An alternative route would be to take the ordinary train on column 3 from (2,3) at time 8 and reach (1,3) at time 10. We then wait there till time 13 and take the fast train on row 1 going left, reaching (1,1) at time 15. You can verify that there is no way of reaching (1,1) earlier than that.

Input format

The first line contains two integers *M* and *N*
indicating the number rows and columns in the metro system. This is
followed by *M* lines, lines 2, 3, …, *M*+1,
describing the trains along the *M* rows. The first letter
on each line is either `F` or `O` or `S`,
indicating whether the train is a fast train, an ordinary train or
a slow train. Following this, separated by a blank space, is an
integer indicating the time at which this train starts running. The
next *N* lines, lines *M*+2, *M*+3, …,
*N*+*M*+1, contain similar descriptions of the trains
along the *N* columns. The last line, line
*N*+*M*+2, contains 5 integers *a*,
*b*, *c*, *d* and *e* where
*(a,b)* is the starting station, *c* is the starting
time and *(d,e)* is the destination station.

Output format

A single integer indicating the earliest time at which one may reach the destination.

Test Data:

You may assume that *M*, *N* ≤ 50.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

3 4 F 3 S 2 O 2 S 1 F 2 O 2 F 4 2 3 8 1 1

Sample Output

15

CPU Timelimit: | 3 seconds |

Memory limit: | 64M |

Grading style: | ioi |