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.

0 0
4 6
3
DDD

5

## HINT

Eve can choose not to move at every minute.

[Submit][Status]