Indian National Olympiad in Informatics

Related:

Online Programming Contest, 15-16 April, 2006

IARCS home > OLYMPIAD

Advanced Division

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

Sample Output