#1993 공간을 지배하는 자

1 s   128 MB  

Description

 

금요일은 대학생들과 젊은 직장인들 사이에서 소위 불금(불타는 금요일)이라 불려지는 신성한 날이다. A대학교에 재학중인 승규에게 불금이란 클럽에서 춤을 추며 이성에게 자신의 매력 어필을 하는 수 많은 날들 중 하나일 뿐이다. 이번 주도 어김없이 클럽에 가려고 하는 승규는 갑자기 클럽의 어느 위치에서 춤을 춰야 가장 많은 여성들과 함께 불금을 즐길 수 있는지 궁금해졌다. 가로 세로 N미터의 클럽 안에서 승규는 특정한 위치를 중심으로 반경 R미터안에 여성과 함께 불금을 즐기고 있다고 생각한다. 그러나 소심한 승규는 다른 남성이 선택한 여성에게 들이댈 용기가 없다. 그렇기 때문에 “앞뒤좌우에 남성이 서 있는 여성은 함께 있지 않는다”라고 판단한다. 승규는 한 자리에서 가장 많은 여성과 함께 춤을 추며 불금을 보내고 싶다. 그렇다면 하루라도
카사노바가 되고 싶은 승규가 움직이지 않고 한 위치에서 춤을 출 때 얼마나 많은 여성과 함께 불금을 보낼 수 있는지 알려주자.
참고로 승규는 클럽에서 춤 추는걸 좋아하나 부비부비를 극도로 싫어하므로 남자건 여자건 딱 달라 붙지 않는다. ( 부비부비는 같은 좌표에 서는걸 뜻한다.)
(승규와 여성의 거리가 정확히 R인 경우도 함께 불금을 보낸다 생각한다.)

Input

 

테스트 케이스 T가 입력된다. (0 ≤ T ≤ 10)
각 테스트 케이스마다 아래의 정보가 입력된다.
N R M ( N : 가로세로의 길이, R : 위치 중심에서 거리, M : 들어올 사람의 숫자)
S1 X1 Y1 ( S : 성별( 남성 M, 여성 F ), X : 사람의 x좌표, Y : 사람의 y좌표, X, Y는 정수 )
S2 X2 Y2
.
.
.
Sm Xm Ym
(0 < N ≤ 100)
(0 ≤ M ≤ N*N)
(0 < R ≤ N/2)
(0 ≤ Xi, Yi ≤ N)

Output

승규가 함께 불금을 즐기고 있다고 생각하는 여성의 최대 숫자를 출력하여라.

Sample Input

Sample Output

2
3 1 5
M 2 2
F 1 2
F 2 1
F 3 2
F 2 3
9 2 9
M 2 9
M 6 4
F 3 4
F 4 3
F 4 5
F 4 6
F 5 4
F 6 2
F 6 5
0
4

Source

2012 Ajou Programming Contest, Division 2