시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB75613322442166141.025%

문제

'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.

게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.

뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.

  • 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
  • 만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.
  • 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
  • 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

입력

첫째 줄에 보드의 크기 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄에 사과의 개수 K가 주어진다. (0 ≤ K ≤ 100)

다음 K개의 줄에는 사과의 위치가 주어지는데, 첫 번째 정수는 행, 두 번째 정수는 열 위치를 의미한다. 사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열) 에는 사과가 없다.

다음 줄에는 뱀의 방향 변환 횟수 L 이 주어진다. (1 ≤ L ≤ 100)

다음 L개의 줄에는 뱀의 방향 변환 정보가 주어지는데, 정수 X와 문자 C로 이루어져 있으며. 게임 시작 시간으로부터 X초가 끝난 뒤에 왼쪽(C가 'L') 또는 오른쪽(C가 'D')로 90도 방향을 회전시킨다는 뜻이다. X는 10,000 이하의 양의 정수이며, 방향 전환 정보는 X가 증가하는 순으로 주어진다.

출력

첫째 줄에 게임이 몇 초에 끝나는지 출력한다.

예제 입력 1

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

예제 출력 1

9

예제 입력 2

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

예제 출력 2

21

예제 입력 3

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

예제 출력 3

13
W3sicHJvYmxlbV9pZCI6IjMxOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjNDAiLCJkZXNjcmlwdGlvbiI6IjxwPiAmIzM5O0R1bW15JiMzOTsgXHViNzdjXHViMjk0IFx1YjNjNFx1YzJhNFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWIyOTQgXHViYzQwXHVjNzc0IFx1YjA5OFx1YzY0MFx1YzExYyBcdWFlMzBcdWM1YjRcdWIyZTRcdWIyYzhcdWIyOTRcdWIzNzAsIFx1YzBhY1x1YWNmY1x1Yjk3YyBcdWJhMzlcdWM3M2NcdWJhNzQgXHViYzQwIFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWIyOThcdWM1YjRcdWIwOWNcdWIyZTQuIFx1YmM0MFx1Yzc3NCBcdWM3NzRcdWI5YWNcdWM4MDBcdWI5YWMgXHVhZTMwXHVjNWI0XHViMmU0XHViMmM4XHViMmU0XHVhYzAwIFx1YmNiZCBcdWI2MTBcdWIyOTQgXHVjNzkwXHVhZTMwXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmFiOFx1YWNmYyBcdWJkODBcdWI1MmFcdWQ3ODhcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIE54TiBcdWM4MTVcdWMwYWNcdWFjMDEgXHViY2Y0XHViNGRjXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzljNFx1ZDU4OVx1YjQxOFx1YWNlMCwgXHViYTg3XHViYTg3IFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWFjMDAgXHViMTkzXHVjNWVjXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHVjNzU4IFx1YzBjMVx1ZDU1OFx1Yzg4Y1x1YzZiMCBcdWIwNWRcdWM1ZDAgXHViY2JkXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzc0IFx1YzJkY1x1Yzc5MVx1ZDU2MFx1YjU0YyBcdWJjNDBcdWM3NDAgXHViOWU4XHVjNzA0IFx1YjllOFx1Yzg4Y1x1Y2UyMVx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjZTAgXHViYzQwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YjJlNC4gXHViYzQwXHVjNzQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3NDQgXHVkNWE1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjNDBcdWM3NDAgXHViOWU0IFx1Y2QwOFx1YjljOFx1YjJlNCBcdWM3NzRcdWIzZDlcdWM3NDQgXHVkNTU4XHViMjk0XHViMzcwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAgXHViYzQwXHVjNzQwIFx1YmFiOFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWIyOThcdWI4MjQgXHViYTM4XHViOWFjXHViOTdjIFx1YjJlNFx1Yzc0Y1x1Y2U3OFx1YzVkMCBcdWM3MDRcdWNlNThcdWMyZGNcdWQwYThcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljY1x1YzU3ZCBcdWJjYmRcdWM3NzRcdWIwOTggXHVjNzkwXHVhZTMwXHVjNzkwXHVjMmUwXHVjNzU4IFx1YmFiOFx1YWNmYyBcdWJkODBcdWI1MmFcdWQ3ODhcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHVjMGFjXHVhY2ZjXHVhYzAwIFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1Y2U3OFx1YzVkMCBcdWM3ODhcdWIzNTggXHVjMGFjXHVhY2ZjXHVhYzAwIFx1YzVjNlx1YzViNFx1YzljMFx1YWNlMCBcdWFmMmNcdWI5YWNcdWIyOTQgXHVjNmMwXHVjOWMxXHVjNzc0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViOWNjXHVjNTdkIFx1Yzc3NFx1YjNkOVx1ZDU1YyBcdWNlNzhcdWM1ZDAgXHVjMGFjXHVhY2ZjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCwgXHViYWI4XHVhZTM4XHVjNzc0XHViOTdjIFx1YzkwNFx1YzVlY1x1YzExYyBcdWFmMmNcdWI5YWNcdWFjMDAgXHVjNzA0XHVjZTU4XHVkNTVjIFx1Y2U3OFx1Yzc0NCBcdWJlNDRcdWM2Y2NcdWM5MDBcdWIyZTQuIFx1Yzk4OSwgXHViYWI4XHVhZTM4XHVjNzc0XHViMjk0IFx1YmNjMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjMGFjXHVhY2ZjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWJjNDBcdWM3NTggXHVjNzc0XHViM2Q5XHVhY2JkXHViODVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWJhODcgXHVjZDA4XHVjNWQwIFx1YjA1ZFx1YjA5OFx1YjI5NFx1YzljMCBcdWFjYzRcdWMwYjBcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMCBcdWMwYWNcdWFjZmNcdWM3NTggXHVhYzFjXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IEsgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBLXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM4MTVcdWMyMThcdWIyOTQgXHVkNTg5LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM1ZjQgXHVjNzA0XHVjZTU4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjMGFjXHVhY2ZjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWJhYThcdWI0NTAgXHViMmU0XHViOTc0XHViYTcwLCBcdWI5ZTggXHVjNzA0IFx1YjllOCBcdWM4OGNcdWNlMjEgKDFcdWQ1ODkgMVx1YzVmNCkgXHVjNWQwXHViMjk0IFx1YzBhY1x1YWNmY1x1YWMwMCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzQwXHVjNzU4IFx1YmMyOVx1ZDVhNSBcdWJjYzBcdWQ2NTggXHVkNjlmXHVjMjE4IEwgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBMICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzQwXHVjNzU4IFx1YmMyOVx1ZDVhNSBcdWJjYzBcdWQ2NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgIFx1YzgxNVx1YzIxOCBYXHVjNjQwIFx1YmIzOFx1Yzc5MCBDXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAuIFx1YWM4Y1x1Yzc4NCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFhcdWNkMDhcdWFjMDAgXHViMDVkXHViMDljIFx1YjRhNFx1YzVkMCBcdWM2N2NcdWNhYmQoQ1x1YWMwMCAmIzM5O0wmIzM5OykgXHViNjEwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZChDXHVhYzAwICYjMzk7RCYjMzk7KVx1Yjg1YyA5MFx1YjNjNCBcdWJjMjlcdWQ1YTVcdWM3NDQgXHVkNjhjXHVjODA0XHVjMmRjXHVkMGE4XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gWFx1YjI5NCAxMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmMyOVx1ZDVhNSBcdWM4MDRcdWQ2NTggXHVjODE1XHViY2Y0XHViMjk0IFhcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViYTg3IFx1Y2QwOFx1YzVkMCBcdWIwNWRcdWIwOThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMxOTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ6bWlqYSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIG9mIHRoZSBtb3N0IHBvcHVsYXIgRE9TIGdhbWVzIGlzICYjMzk7RHVtbXkmIzM5Oy4gVGhlIHNuYWtlIGlzIGNyYXdsaW5nIHRocm91Z2ggdGhlIGJvYXJkIGFuZCBlYXRpbmcgYXBwbGVzIHRoYXQgaW5jcmVhc2UgaXRzIGxlbmd0aC4gVGhlIGdhbWUgZW5kcyB3aGVuIHRoZSBzbmFrZSBidW1wcyBpbnRvIGl0c2VsZiBvciBpbnRvIHRoZSB3YWxsLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HYW1lIGJvYXJkIGNvbnNpc3RzIG9mIE54TiBzcXVhcmVzIGFycmFuZ2VkIGluIE4gcm93cyBhbmQgTiBjb2x1bW5zLCBhbmQgc29tZSBzcXVhcmVzIGNvbnRhaW4gYXBwbGVzLiBBcm91bmQgdGhlIGJvYXJkIHRoZXJlIGlzIGEgd2FsbC4gQXQgdGhlIGJlZ2lubmluZyBvZiB0aGUgZ2FtZSwgdGhlIHNuYWtlIGlzIGxvY2F0ZWQgaW4gdGhlIHRvcC1sZWZ0IGNvcm5lciwgaXRzIGxlbmd0aCBpcyBlcXVhbCB0byAxIGFuZCBpdHMgaGVhZCBpcyBkaXJlY3RlZCB0b3dhcmRzIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbmFrZSBpcyBjcmF3bGluZyBieSBjaGFuZ2luZyBpdHMgcG9zaXRpb24gZHVyaW5nIGVhY2ggc2Vjb25kIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGVzOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmZpcnN0LCBzbmFrZSBleHRlbmRzIGl0cyBsZW5ndGggYnkgc3ByZWFkaW5nIHRvIHRoZSBuZXh0IHNxdWFyZSBpbiBmcm9udCBvZiB0aGUgaGVhZCAoaS5lLiBpbiB0aGUgZGlyZWN0aW9uIG9mIHRoZSBoZWFkKSw8XC9saT5cclxuXHQ8bGk+aWYgdGhlcmUgaXMgYW4gYXBwbGUgb24gdGhhdCBzcXVhcmUsIHRhaWwgb2YgdGhlIHNuYWtlIGRvZXMgbm90IG1vdmUgKGhlbmNlLCBpdHMgbGVuZ3RoIGlzIGluY3JlYXNlZCBieSAxIGluIHRoaXMgc3RlcCksPFwvbGk+XHJcblx0PGxpPmlmIHRoZXJlIGlzIG5vIGFwcGxlLCBsYXN0IHNxdWFyZSBvZiB0aGUgdGFpbCBpcyBlcmFzZWQgKGhlbmNlLCBpdHMgbGVuZ3RoIHN0YXlzIHVuY2hhbmdlZCkmbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Qb3NpdGlvbnMgb2YgdGhlIGFwcGxlcyBhbmQgbW92ZW1lbnRzIG9mIHRoZSBzbmFrZSBhcmUgZ2l2ZW4uIFdyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBudW1iZXIgb2Ygc2Vjb25kcyB1bnRpbCB0aGUgZ2FtZSBlbmRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDIgJmxlOyBOICZsZTsgMTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb2xsb3dpbmcgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIEssIDAgJmxlOyBLICZsZTsgMTAwLCB0aGUgbnVtYmVyIG9mIGFwcGxlcyBvbiB0aGUgYm9hcmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyBLIGxpbmVzIGNvbnRhaW4gY29vcmRpbmF0ZXMgb2YgYXBwbGVzIG9uIHRoZSBib2FyZC4gRmlyc3QgbnVtYmVyIGRlbm90ZXMgdGhlIHJvdyBhbmQgc2Vjb25kIG51bWJlciBkZW5vdGVzIHRoZSBjb2x1bW4gb2YgdGhlIGJvYXJkIHdoZXJlIHRoZSBhcHBsZSBpcyBzaXR1YXRlZC4gVGhlcmUgd2lsbCBiZSBubyBhcHBsZSBhdCB0aGUgdG9wLWxlZnQgY29ybmVyIG9mIHRoZSBib2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9sbG93aW5nIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBudW1iZXIgTCwgMSAmbGU7IEwgJmxlOyAxMDAsIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIHNuYWtlIG1ha2VzIGEgdHVybi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIEwgbGluZXMgY29udGFpbnMgdGhlIGRlc2NyaXB0aW9uIG9mIG9uZSB0dXJuLiBBIHNpbmdsZSB0dXJuIGlzIGRlc2NyaWJlZCBieSBhIG51bWJlciBYIChwb3NpdGl2ZSBpbnRlZ2VyIGxlc3MgdGhhbiBvciBlcXVhbCB0byAxMCwwMDApIGFuZCBhIGNoYXJhY3RlciBDLiBUaGlzIG1lYW5zIHRoYXQgdGhlIHNuYWtlIHJvdGF0ZXMgaXRzIGhlYWQgOTAgZGVncmVlcyBsZWZ0IChpZiBDIGlzICYjMzk7TCYjMzk7KSBvciByaWdodCAoaWYgQyBpcyAmIzM5O0QmIzM5OykgYXQgdGhlIGVuZCBvZiB0aGUgWHRoIHNlY29uZCZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIG51bWJlciBvZiBzZWNvbmRzIGZyb20gdGhlIHByb2JsZW0gc3RhdGVtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #1 - Juniors 2번