Snake Game là trò chơi điện tử DOS rất nổi tiếng. Trong trò chơi này, một con rắn bò quanh màn hình và ăn các quả táo để tăng thêm độ dài. Trò chơi kết thúc khi con rắn cắn vào chính mình hoặc đi vào tường rào. Màn hình trò chơi hình vuông, có tường rào bao quanh và được chia thành ~N \times N~ ô vuông đơn vị, vài ô vuông trong vùng con rắn bò có chứa quả táo.

Khi trò chơi bắt đầu, con rắn có chiều dài ~1~, tại ô vuông góc trên bên trái và đầu của nó hướng về bên phải. Con rắn sẽ thay đổi vị trí trong mỗi giây theo quy tắc sau:

• Đầu tiên, con rắn bò đến ô vuông kề bên phải vị trí hiện tại (theo hướng đầu con rắn).
• Nếu ô vuông con rắn bò đến có một quả táo thì đuôi của con rắn không di chuyển (trong trường hợp này, chiều dài của con rắn tăng thêm ~1~ ô vuông đơn vị).
• Nếu ô vuông con rắn bò đến không có quả táo thì con rắn bị xóa ~1~ ô vuông đơn vị ở vị trí cuối cùng của đuôi (trong trường hợp này, độ dài của con rắn không thay đổi).

Yêu cầu

Cho trước vị trí của các quả táo và các bước di chuyển của con rắn. Hãy viết chương trình tính xem trò chơi sẽ kết thúc sau bao nhiêu giây.

Dữ liệu vào

• Dòng đầu chứa số ~N~ ~(1 \leq N \leq 100)~.
• Dòng thứ hai chứa số nguyên ~K~ ~(1 \leq K \leq 100)~, là số quả táo.
• ~K~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~x, y~ là vị trí ô vuông chứa quả táo (số đầu tiên là hàng và số thứ hai là cột). Không có quả táo ở ô góc trên bên trái.
• Dòng tiếp theo chứa số nguyên ~L~ ~(1 \leq L \leq 100)~, là số lần đổi hướng di chuyển của con rắn.
• ~L~ dòng tiếp theo, mỗi dòng gồm ~1~ số nguyên ~X~ ~(1 \leq X \leq 10000)~, và ~1~ kí tự ~C~, mô tả một lần đổi hướng di chuyển của con rắn: Sau ~X~ giây, nếu con rắn quay đầu sang trái thì kí tự ~C~ có giá trị là L, nếu con rắn quay đầu sang phải thì kí tự ~C~ có giá trị là D.

Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.

Kết quả ra

Một số nguyên ~S~ là thời gian trò chơi kết thúc.

Sample Input

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

Sample Output

13