시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16 1 1 33.333%

문제

프로그래밍 대회가 끝난 연정이는 파티를 열기로 결정했다. 그래서 친구들을 초대하여 소주와 맥주를 부어라 마셔라하며 즐겁게 하루를 보냈다. 

파티가 끝난 지금 연정이는 친구들을 안전하게 자신의 집으로 돌아가기를 원한다. 문제는 이들의 집은 너무 멀어 반드시 차를 이용해야한다는 것이다. 

자동차를 이용하기 위해선 아래의 조건은 반드시 만족해야한다.

  • 해당 지역으로 이동하는 자동차에는 반드시 술에 취하지 않은 사람이 의무적으로 한 명 탑승 ( 운전을 해야하므로 ) 하며 해당 지역 이외로는 가지 않는다.
  • 자동차에 빈 자리가 남을 수는 있으나 초과하여 태울 수는 없다.

연정이 집에 놀러온 친구들과 각 지역으로 갈 수 있는 자동차 개수 및 지역 개수가 주어질 때 자동차 자리가 모자라서 또는 집으로 이동 할 자동차가 없어 

어쩔 수 없이 연정이 집에서 자야하는 사람이 몇 명인지 알아내시오.

입력

첫 줄에는 전체 테스트 개수 ( K ) 가 주어진다. ( K ≥ 1 )

다음 줄 부터는 전체 테스트 개수만큼 아래와 같은 형식이 주어진다.

연정이 집에 놀러온 친구 수 ( n ) , 다른 지역으로 이동할 수 있는 자동차 수 ( c ) ,  지역의 수 ( ℓ ) [ n ≤ 500 , c ≤ n , ℓ ≤ c ]

하위 n 개 줄은 각 친구가 사는 지역 번호 [ 지역번호는 1 부터 ℓ 까지 ] 와 취했는지 ( I ) 안 취했는지 ( S ) 를 나타내는 문자로 구성된다.

그 다음 하위 c 개 줄은 이동할 지역 번호 [ 지역번호는 1 부터 ℓ 까지 ] 와 탑승할 수 있는 최대 좌석 개수 ( 2 ~ 8 ) 가 주어진다.

출력

각 테스트에서 연정이 집에서 자야하는 친구의 수를 "Data Set x:" ( "" 제외 ) 형식과 함께 출력하시오.

예제 입력

1
8 3 2
1 I
1 I
1 S
2 I
1 I
1 I
2 S
2 S
1 3
1 3
2 4

예제 출력

Data Set 1:
2

힌트

출처

University > The USC Programming Contest > Spring 2007 F번