12541254 SUSTech Online Judge
Problem 1254 --[Hard] Catch Neko

1254: [Hard] Catch Neko

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 957  Solved: 104
[Submit][Status][Web Board]

Description

Neko is running away! Eve wants to catch him. At first, Eve is standing at the point with coordinates \((x_1,y_1)\), while Neko is standing at the point with coordinates \((x_2,y_2)\). For every minute, Eve can choose to go up, down, left, or right with 1 unit distance. For instance, if she is at \((x,y)\) now, she can go to \((x,y+1),(x,y-1),(x-1,y)\) or \((x+1,y)\).

Eve noticed that Neko also moves 1 unit distance every minute, but he only moves according to a sequence periodically. The sequence only contains 'U','D','L','R', denoting that Neko moves up, down, left, right respectively.

Eve is now wondering how many minutes she needs at least to catch Neko.

Input

The first line contains two integers \(x_1,y_1 (0≤x_1,y_1≤10^9)\) —— the initial coordinate of Eve.

The second line contains two integers \(x_2,y_2 (0≤x_2,y_2≤10^9)\) —— the initial coordinate of Neko.

It is guaranteed that the initial coordinates and destination point coordinates are different.

The third line contains a single integer \(N (1≤N≤10^5)\) —— the length of the sequence \(S\).

The fourth line contains the string \(S\) itself, consisting only four letters \(U, D, L, R\).

Output

Please output the minimum minutes Eve needs to catch Neko. If she can not catch Neko forever, please output -1.

Sample Input

0 0
4 6
3
DDD

Sample Output

5

HINT

Eve can choose not to move at every minute.

Source

[Submit][Status]