ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2155. Quadrocopter

Time limit: 2.0 second
Memory limit: 256 MB
The company NAUMEN is testing the newest software for quadrocopters. Vova, who works in NAUMEN, is tasked with launching a quadrocopter on a cellular field. But suddenly strong wind started blowing, making the quadrocopter uncontrollable! Vova needs to catch it as soon as possible.
The cellular field has h rows, numbered from 1 to h, and w columns, numbered from 1 to w. Each cell has swampiness (integer between 1 and 999 999) and direction of wind (one of four: up, down, left or right).
Vova starts in a cell in row r1 in column c1, and he moves wherever he wants. He can only move to a cell that shares a side with his current cell; that takes the number of seconds equal to the swampiness of the target cell. Formally, to move to a neighboring cell with a swampiness value of x, Vova waits for x seconds and then instantly moves to the chosen cell. Vova can also go nowhere, remaining in his current cell for as long as he wants to.
The quadrocopter starts in a cell in row r2 in column c2, and it moves in the direction of the wind, one cell per second. Formally, at the end of each second, the quadrocopter instantly moves to the neighboring cell in the direction of the wind. Direction up corresponds to a decrease of row number, down — an increase of row number, left — a decrease of column number, right — an increase of column number. If the wind is pointed outside the field, then the quadrocopter leaves the field, making it impossible to catch.
As soon as Vova and the quadrocopter are located in the same cell, Vova catches it. But if Vova arrives in the cell at the same moment as the quadrocopter leaves it, Vova doesn’t catch it yet. Determine if Vova is able to catch the quadrocopter, and find the shortest amount of time to do it.

Input

The first line contains two integers h and w — height and width of the field (1 ≤ h, w ≤ 250; w · h ≠ 1).
The second line contains two integers r1 and c1 — position of Vova’s starting cell (1 ≤ r1h; 1 ≤ c1w).
The third line contains two integers r2 and c2 — position of the quadrocopter’s starting cell (1 ≤ r2h; 1 ≤ c2w). It is guaranteed that Vova and the quadrocopter start in different cells..
Then h lines follow, containing the swampiness of cells. In the i-th of these lines there are w integers from 1 to 999 999 inclusively; j-th of them is equal to the swampiness of the cell in row i in column j.
Then h more lines follow, containing directions of the wind. In the i-th of these lines there are w capital letters “U”, “D”, “L” or “R”, not separated by spaces; j-th of them corresponds to the direction of wind in the cell in row i in column j. The letter “U” means up, “D” — down, “L” — left, “R” — right.

Output

If Vova is unable to catch the quadrocopter, output a single integer −1. Otherwise, output the least possible amount of seconds in which Vova is able to catch the quadrocopter.

Samples

inputoutput
2 7
1 1
1 4
1 1 1 1 1 1 1
1 1 1 1 1 1 1
RDRDRDR
URURURU
7
2 6
1 1
1 4
1 1 1 1 1 1
1 1 1 1 1 1
RDRDRD
URURUR
-1
3 3
2 2
1 1
8 9 8
8 8 8
8 8 8
RRD
URD
ULL
9
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2020