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.
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 ≤ r1 ≤ h; 1 ≤ c1 ≤ w).
The third line contains two integers r2 and c2 — position of the quadrocopter’s starting cell (1 ≤ r2 ≤ h; 1 ≤ c2 ≤ w). 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 “
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.
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.
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
8 9 8
8 8 8
8 8 8
Problem Author: Valentin Zuev
Problem Source: Ural School Programming Contest 2020