zmija

문제

One of the most popular DOS games is 'Dummy'. The snake is crawling through the board and eating apples that increase its length. The game ends when the snake bumps into itself or into the wall. 

Game board consists of NxN squares arranged in N rows and N columns, and some squares contain apples. Around the board there is a wall. At the beginning of the game, the snake is located in the top-left corner, its length is equal to 1 and its head is directed towards right. 

Snake is crawling by changing its position during each second according to the following rules: 

• first, snake extends its length by spreading to the next square in front of the head (i.e. in the direction of the head),
• if there is an apple on that square, tail of the snake does not move (hence, its length is increased by 1 in this step),
• if there is no apple, last square of the tail is erased (hence, its length stays unchanged) 

Positions of the apples and movements of the snake are given. Write a program that will calculate the number of seconds until the game ends. 

입력

First line of input contains an integer N, 2 ≤ N ≤ 100. 

Following line contains an integer K, 0 ≤ K ≤ 100, the number of apples on the board. 

Following K lines contain coordinates of apples on the board. First number denotes the row and second number denotes the column of the board where the apple is situated. There will be no apple at the top-left corner of the board. 

Following line contains an integer number L, 1 ≤ L ≤ 100, the number of times the snake makes a turn. 

Each of the following L lines contains the description of one turn. A single turn is described by a number X (positive integer less than or equal to 10,000) and a character C. This means that the snake rotates its head 90 degrees left (if C is 'L') or right (if C is 'D') at the end of the Xth second 

출력

First and only line of output should contain number of seconds from the problem statement. 

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

9

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

21

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

13