Công ty X-TRANS đang sản xuất robot vận chuyển hàng hóa tự động trên mặt đất. Để làm việc đó, X-TRANS tiến hành huấn luyện robot trên một địa hình phẳng được chia thành một lưới các ô vuông gồm m dòng (đánh số từ 1 đến m) và n cột (đánh số từ 1 đến n).

Robot của X-TRANS có kích thước bằng đúng một ô vuông và có thể thực hiện các lệnh di chuyển đến các ô liền cạnh với ô đang đứng. Giả sử robot đang đứng ở ô (X, Y), nó có thể thực hiện một trong bốn lệnh di chuyển sau:

• U: robot di chuyển đến ô (X-1, Y)
• D: robot di chuyển đến ô (X+1, Y)
• L: robot di chuyển đến ô (X, Y-1)
• R: robot di chuyển đến ô (X, Y+1)

Để mô hình huấn luyện gần với địa hình thực tế, X-TRANS đặt các vật cản tại p ô vuông phân biệt trên lưới địa hình để không cho robot đi vào. Robot chỉ có thể thực hiện một lệnh di chuyển nếu như ô mà nó di chuyển đến nằm bên trong lưới địa hình và không chứa vật cản. Nếu robot không thể thực hiện một lệnh, nó sẽ bỏ qua lệnh đó và tiến hành thực hiện lệnh tiếp theo.

X-TRANS tiến hành thử nghiệm robot với một tập gồm k lệnh để kiểm tra xem robot có thể di chuyển từ ô (1,1) và kết thúc tại ô (m, n) sau khi thực hiện lần lượt các lệnh này được hay không. Nếu robot không kết thúc tại ô (m, n), X-TRANS cần tìm cách xóa đi một số ít nhất các lệnh trong tập k lệnh để robot sẽ kết thúc tại ô (m, n) sau khi thực hiện tập các lệnh còn lại.

Input:

• Dòng đầu tiên là chứa 4 số nguyên: m, n, p, k (2 ≤ m, n ≤ 40; k ≤ 200);

• Dòng thứ hai chứa một xâu gồm k kí tự thể hiện k lệnh điều khiển robot;

• p dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương x và y cho biết có đặt một vật cản tại ô (x, y). Không đặt vật cản tại hai ô (1,1) và (m, n).

Output:

Ghi một số nguyên là số lượng ít nhất các lệnh cần xóa để robot sẽ kết thúc tại ô (m, n) sau khi thực hiện tập các lệnh còn lại. Nếu không tồn tại cách xóa để di chuyển robot đến ô (m, n) thì ghi ra -1.

Sample Input

5 5 2 12  
RDDDDRRRRRUD 
2 2  
5 3

Sample Output

3

Giải thích

Nếu robot thực hiện tập lệnh RDDDDRRRRRUD, nó sẽ kết thúc tại ô (2,5). Để robot kết thúc tại ô (5,5), X-TRANS cần xóa 3 lệnh để robot thực hiện tập lệnh còn lại là DDDRRRRRD.