문제
존 농부(Farmer John)는 자신의 농장에서 생산되는 우유의 뛰어난 품질로 널리 알려져 있다. 그는 자신의 가장 친한 친구 N명(1 ≤ N ≤ 50)을 초대해 우유 시음 파티를 열고 있다. 안타깝게도, 파티에 준비된 M가지 종류의 우유(1 ≤ M ≤ 50) 중 정확히 한 종류가 상해버렸지만, 존 농부는 어느 것이 상한 우유인지 알지 못한다. 상한 우유를 마신 사람은 파티 도중이든 파티가 끝난 이후든 언젠가 병이 나게 된다.
당신은 파티 기록을 넘겨받았다. 이 기록에는 “누가, 어떤 우유를, 언제 마셨는지”와 “누가, 언제 아팠는지”에 대한 정보가 담겨 있다. 이 정보를 바탕으로, 어떤 우유들이 “상한 우유일 가능성이 있는지”를 추론할 수 있다. 이 사실을 이용해서, 존 농부가 파티 도중이나 파티 이후에 아프게 되는 모든 사람을 반드시 치료할 수 있도록 하기 위해, 최소 몇 번분의 약(약의 복용 횟수, 즉 치료해야 할 사람 수만큼)을 준비해야 하는지 구하는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 정수 N, M, D, S가 주어진다.
다음 D줄(1 ≤ D ≤ 1000)에는 각 줄마다 정수 p, m, t가 주어지며, 이는 사람 p가 시간 t에 우유 m을 마셨음을 의미한다. p의 값은 1…N 범위, m의 값은 1…M 범위, t의 값은 1…100 범위이다. 한 사람이 같은 우유를 여러 번 마실 수도 있고, 같은 시각에 여러 종류의 우유를 마실 수도 있다.
그 다음 S줄(1 ≤ S ≤ N)에는 각 줄마다 정수 p, t가 주어지며, 이는 사람 p가 시간 t에 아프게 되었음을 의미한다. p의 값은 1…N 범위, t의 값은 1…100 범위이다. 각 사람은 많아야 한 번만 아프며, 아프게 되는 유일한 이유는 어떤 시점에 상한 우유를 마셨기 때문인데, 그 시점은 반드시 아픈 시각보다 “엄밀히 이전”이어야 한다(즉, 마신 시간 < 아픈 시간).
출력
정수 하나를 출력한다. 이 정수는 존 농부가 파티 도중과 이후에 아프게 되는 모든 사람을 치료하기 위해, 항상 충분한 양의 약을 확보할 수 있도록 하기 위해 필요한 약의 최소 복용 횟수를 나타낸다.
예제
3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 8
3
사람은 3명이고 우유 종류는 4가지이다. 1번 사람은 시각 3에 아프게 되고, 2번 사람은 시각 8에 아프게 된다. 3번 사람은 파티 동안에는 아프지 않지만, 파티가 끝난 뒤에 아프게 될 가능성은 여전히 고려해야 한다. 이제 어떤 우유가 상했을 수 있는지 보기 위해, 우유 종류를 하나씩 살펴보자. “어떤 우유가 상했을 가능성이 있다”는 말은, 아프게 된 모든 사람이 그 우유를 아프기 전에 마셨다는 뜻이다.
우유 1: 아픈 사람 둘(1번과 2번)이 모두 아프기 전에 이 우유를 마셨으므로, 이 우유는 상한 우유일 수 있다. 이 경우 3번 사람도 이 우유를 마셨으므로, 총 3명이 아프게 된다(3번 사람은 파티가 끝난 뒤에 아프게 됨).
우유 2: 아픈 사람 둘이 모두 아프기 전에 이 우유를 마셨으므로, 이 우유 역시 상한 우유일 수 있다. 이 우유를 마신 다른 사람은 없으므로, 이 우유가 상했다면 최대로 아프게 되는 사람 수는 2명이다.
우유 3: 이 우유는 상한 우유일 수 없다. 왜냐하면 1번 사람이 아프기 전에 이 우유를 마시지 않았기 때문이다. 1번 사람은 시각 4에 이 우유를 마셨고, 시각 3에 아팠다. 우유 3이 1번 사람의 병의 원인이 되려면, 1번 사람은 늦어도 시각 2까지는 이 우유를 마셨어야 한다.
우유 4: 이 우유 역시 상한 우유일 수 없다. 2번 사람은 이 우유를 전혀 마시지 않았는데, 2번 사람도 아프게 되었기 때문이다.
따라서 정답은 존 농부가 약을 3회분 준비해야 한다는 것이다. 왜냐하면, 만약 우유 1이 상한 우유라면 아프게 되는 사람이 총 3명이 되기 때문이다.
로그인해야 코드를 작성할 수 있어요.