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\) hàng (đánh số từ \(1 .. m\)) và \(n\) cột (đánh số từ \(1 ... 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 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ó cầ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ẽ hủy 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 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. Giả sử robot đang đứng ở ô \((1,1)\) trên lưới địa hình được mô tả như hình trên (các ô màu xám chứa các vật cản), 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\).

Dữ liệu

Vào từ thiết bị vào chuẩn có cấu trúc như sau:

• Dòng đầu tiên chứa \(4\) số nguyên: \(m, n, p, k\) \((1 ≤ m, n ≤ 50, 1 \le p, k ≤ 500)\).
• 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 hai 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)\).

Kết quả

Đưa ra thiết bị ra chuẩn 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, ghi ra \(-1\).

Ví dụ:

Dữ liệu:

5 5 2 12
RDDDDRRRRRUD
2 2
5 3

Kết quả:

3

Subtask

\(50\%\) số test có \(k \le 30\).