스트레칭

시간 제한2초메모리 제한2048 MB

요약
K개의 스트레칭을 한 기록과 학생들의 지루함 여부가 최대 50번 주어질 때, 알 수 없는 아침 스트레칭 동작 하나를 확정하는 데 필요한 추가 수업 횟수를 구한다.
난이도

보통10점 중 6점

유형
구현, 완전 탐색, 조합론, 그리디
정답자
아직 제출이 없습니다

문제

서울과학고 체육 선생님인 김 선생님은 수업을 시작하기 전, 부상을 예방하기 위해 학생들에게 스트레칭을 지도합니다. 선생님은 매 체육시간마다 자신이 알고 있는 NN개의 스트레칭 동작 중에서 매번 임의로 KK개를 골라 몸풀기 스트레칭을 진행합니다.

하지만 1학년 7반 학생들은 매일 있는 아침 조회 시간에 조 선생님과 함께 항상 동일한 스트레칭 동작 11가지를 합니다. 문제는 이 동작이 김 선생님이 알고 있는 NN개의 스트레칭 동작 중 하나라는 점입니다. 따라서 체육 시간에 이 동작을 포함하면 학생들은 아침 조회때와 1교시 체육시간에 같은 동작을 반복하게 되어 지루함을 느끼게 됩니다.

김 선생님은 1학년 7반 학생들의 반응을 통해 아침 조회에서 하는 스트레칭 동작을 알아내려고 합니다. 이미 진행된 RR번의 체육 수업 기록과 학생 반응을 바탕으로, 해당 동작을 알아내기 위해 김 선생님이 추가로 몇 번의 체육 수업을 더 해야 하는지를 계산하는 프로그램을 작성하세요.

입력

첫째 줄에 NN, KK, RR이 공백으로 구분되어 주어집니다.

이후 RR번의 체육 수업 기록이 각각 2개의 줄에 걸쳐 제시됩니다.

체육 수업 기록의 첫 번째 줄에는 해당 체육 수업에서 진행한 KK개의 스트레칭 동작 번호가 공백으로 구분되어 주어집니다. 김 선생님이 알고 있는 스트레칭 동작은 11번부터 NN번까지 번호가 붙어 있습니다.

체육 수업 기록의 두 번째 줄에는 학생들의 반응이 주어집니다. 학생들이 지루함을 느꼈다면 \tt{unsatisfied}, 그렇지 않았다면 \tt{satisfied}가 주어집니다.

출력

추가로 몇 번의 체육 수업을 더 해야 김 선생님이 아침 조회 스트레칭 동작을 알아낼 수 있음이 보장되는지를 출력합니다.

만약 추가적인 정보 없이 주어진 정보로만 해당 동작을 알아낼 수 있다면 00을 출력합니다.

제한

  • 1≤K<N≤100,0001 \le K < N \le 100\\,000
  • 1≤R≤501 \le R \le 50
  • 입력 데이터에 모순은 없습니다.

예제1

  1. 예제 1

    입력
    20 5 3
1 2 3 4 5
unsatisfied
5 6 7 8 9
unsatisfied
9 10 11 12 13
satisfied
    예상 출력
    0