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 và ~n~ cột. Robot 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:

• 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)~

X-TRANS đặt các vật cản tại ~p~ ô vuông phân biệt trên lưới. Robot chỉ có thể thực hiện một lệnh di chuyển nếu ô đích nằm trong lưới 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. 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ố nhiều 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.

Yêu cầu: Hãy tìm số lượng nhiều nhất các lệnh cần xóa để robot sẽ kết thúc tại ô ~(m, n)~. Nếu không tồn tại cách xóa, ghi ra -1.

Input

• Dòng đầu tiên chứa 4 số nguyên: ~m, n, p, k~ (~2 \le m \times n \le 5000~);
• 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;
• ~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 ra một số nguyên là số lượng nhiều nhất các lệnh cần xóa. Nếu không tồn tại cách xóa, ghi ra -1.