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:-----
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:-----
A single integer indicating the earliest time at which one may reach the destination.

-----Constraints:-----
- $1 \leq M, N \leq 50$.
- $1 \leq a, d \leq M$
- $1 \leq b, e \leq N$
- $1 \leq$ all times in input $\leq 20$

-----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

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from queue import PriorityQueue
(m, n) = list(map(int, input().split()))
rr = []
cc = []
speed = {'S': 3, 'O': 2, 'F': 1}
visited = set()
dp = []

def qwerty(cur, x, y, f):
	if f == 0:
		gg = rr[x][1] + y * rr[x][0]
		while gg < cur:
			gg += 2 * (n - 1) * rr[x][0]
		return gg - cur + rr[x][0]
	elif f == 1:
		gg = rr[x][1] + (2 * (n - 1) - y) * rr[x][0]
		while gg < cur:
			gg += 2 * (n - 1) * rr[x][0]
		return gg - cur + rr[x][0]
	elif f == 2:
		gg = cc[y][1] + x * cc[y][0]
		while gg < cur:
			gg += 2 * (m - 1) * cc[y][0]
		return gg - cur + cc[y][0]
	elif f == 3:
		gg = cc[y][1] + (2 * (m - 1) - x) * cc[y][0]
		while gg < cur:
			gg += 2 * (m - 1) * cc[y][0]
		return gg - cur + cc[y][0]
dirx = [0, 0, 1, -1]
diry = [1, -1, 0, 0]
for i in range(m):
	o = [x for x in input().split()]
	o[0] = speed[o[0]]
	o[1] = int(o[1])
	rr.append(o)
for i in range(n):
	o = [x for x in input().split()]
	o[0] = speed[o[0]]
	o[1] = int(o[1])
	cc.append(o)
(sx, sy, stt, dx, dy) = list(map(int, input().split()))
sx -= 1
sy -= 1
dx -= 1
dy -= 1
for i in range(m):
	dp.append([10 ** 9] * n)
dp[sx][sy] = stt
pq = PriorityQueue()
pq.put((stt, sx, sy))
while not pq.empty():
	(t, cxx, cyy) = pq.get()
	if (cxx, cyy) in visited:
		continue
	visited.add((cxx, cyy))
	for i in range(len(dirx)):
		nxx = cxx + dirx[i]
		nyy = cyy + diry[i]
		if nxx >= 0 and nxx < m and (nyy >= 0) and (nyy < n) and ((nxx, nyy) not in visited):
			coo = qwerty(dp[cxx][cyy], cxx, cyy, i)
			if coo + dp[cxx][cyy] < dp[nxx][nyy]:
				dp[nxx][nyy] = coo + dp[cxx][cyy]
				pq.put((dp[nxx][nyy], nxx, nyy))
print(dp[dx][dy])