시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 315 58 52 24.528%

문제

코로나 바이러스로 사회적 거리두기가 한창이다. 하지만 이러한 시국 이전에도 거리두기가 잘 지켜지던 곳이 있었으니... 바로 독서실이다.

독서실에서 관리자로 근무 중이던 민규는 놀라운 사실을 발견했다. 사람들은 항상 서로 더 멀리 앉으려고 노력한다는 것이었다.

민규는 이러한 사실을 관찰하여 잘 정리해보았다.

  1. 사람들은 가장 가까이에 앉아있는 사람이 가장 먼 자리를 선호한다. 만약 독서실을 이용하는 사람이 없다면 좌석번호 1번 자리를 가장 선호한다.
  2. 1번 규칙으로 비교할 수 없다면, 가장 먼 좌석들 중에서 좌석 번호가 가장 작은 자리를 선호한다.

독서실 관리자로 오래 근무한 민규에게는 선호하는 좌석이 있다. 하지만 민규는 매우 소심하기 때문에, 사람들이 본인 때문에 이용하고자하는 자리를 이용하지 못하는 일은 피하고 싶다.

민규가 근무하는 독서실은 09:00 부터 21:00 까지 운영되며, 철저히 예약제로 운영되기 때문에 민규는 사람들이 언제부터 언제까지 독서실을 이용하는지 알 수 있다.

이러한 정보를 토대로, 민규는 자신이 선호하는 자리를 얼마나 이용할 수 있는지 계산해보고자 한다.

입력

첫 번째 줄에 독서실 좌석의 개수 N, 독서실 예약자 수 T, 민규가 좋아하는 좌석 번호 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 500, 1 ≤ P ≤ N)

다음 T 개의 줄에는 독서실 입실 시간, 독서실 퇴실 시간이 HHMM HHMM 형태로 입력된다.

(0900 ≤ HHMM ≤ 2100, 0910 0900와 같이 퇴실 시간이 입실 시간보다 빠른 경우는 없다)

출력

민규가 선호하는 좌석을 이용할 수 있는 시간이 총 몇분인지 출력하시오.

제한

독서실의 모든 좌석은 비어있는 상태로 시작한다.

독서실 예약이 같은 시각에 시작된다면 짧은 이용시간을 가진 사람을 먼저 앉힌다.

독서실 예약 리스트에 있는 예약자들이 좌석이 없어서 못 앉는 상태는 존재하지 않는다.

민규는 선호하는 좌석을 얼마나 이용할 수 있는지 계산하고 싶어하는 것이기 때문에 예약인원들이 자리를 이용하는 것에 영향을 주지 않는다.

예제 입력 1

5 6 1
0915 0930
0940 2040
0910 0920
2040 2050
2043 2047
2044 2046

예제 출력 1

40


09:00 ~ 09:10 시간에는 1번 자리가 비워져 있으므로 민규가 앉을 수 있다. = 10분

09:10 에는 3번 예약자가 와서 규칙에 따라 1번 좌석을 이용한다.

09:15 에는 1번 예약자가 와서 규칙에 따라 5번 좌석을 이용한다.

3번 예약자는 09:20에 퇴실이므로 민규는 09:20 ~ 09:40 시간에 1번 좌석에 앉을 수 있다. = 20분

09:30 에는 1번 예약자가 사용을 완료하여 퇴실한다.

09:40 에는 2번 예약자가 와서 규칙에 따라 1번 좌석을 이용한다.

20:40 에는 2번 예약자가 사용을 완료하여 퇴실하고 이어서 4번 예약자가 20:40 부터 1번 좌석사용을 시작한다.

20:43 에는 5번 예약자가 와서 규칙에 따라 5번 자리를 이용한다.

20:44 에는 6번 예약자가 와서 규칙에 따라 3번 자리를 이용한다.

20:46 에는 6번 예약자가 사용을 완료하여 퇴실하고 20:47 에는 5번 이용자가 사용을 완료하여 퇴실한다.

20:50 에는 4번 예약자가 사용을 완료하여 퇴실하므로 민규는 20:50 ~ 21:00 시간에 1번 좌석에 앉을 수 있다. = 10분

10 + 20 + 10 = 40

민규는 선호하는 좌석을 총 40분 이용가능하다.

예제 입력 2

8 6 3
2000 2020
2020 2030
0900 2100
0910 2100
0920 2100
0930 2000

예제 출력 2

720

09:00 에는 3번 예약자가 와서 규칙에 따라 1번 좌석을 이용한다.

09:10 에는 4번 예약자가 와서 규칙에 따라 8번 좌석을 이용한다.

09:20 에는 5번 예약자가 와서 규칙에 따라 4번 좌석을 이용한다.

09:30 에는 6번 예약자가 와서 규칙에 따라 6번 좌석을 이용한다.

20:00 에는 6번 예약자가 사용을 완료하여 퇴실하고 이어서 1번 예약자가 20:00 부터 6번 좌석을 이용한다.

20:20 에는 1번 예약자가 사용을 완료하여 퇴실하고 이어서 2번 예약자가 20:20 부터 6번 좌석을 이용한다.

20:30 에는 2번 예약자가 사용을 완료하여 퇴실한다.

나머지 인원은 독서실이 끝나는 시간인 21:00까지 계속 이용한다.

민규는 09:00 ~ 21:00 내내 선호하는 좌석을 이용할 수 있다.

민규는 선호하는 좌석을 총 720분 이용가능하다.

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2020 A번