문제
농부 반디는 N명의 친구들을 자기 농장으로 불렀다.
M종류의 우유에 대한 품평회를 하기 위해서이다.
불행히도 M종류의 우유 중 하나가 상한 우유라는 것을 알게 되었다.
냉장 창고 중 하나가 고장 났기 때문이다.
상한 우유를 먹은 사람은, 마신 시점 이후에 배가 아프게 된다.
배가 아픈 시점은, 품평회 중일 수도 있고, 품평회가 끝난 후일 수도 있다.
이는 약 한 알로 치료할 수 있다.
농부 반디는 품평회의 시간 기록을 모두 가지고 있다.
누가 어느 시점에 어느 우유를 마셨는지, 누가 어느 시점에 배 아픔을 호소했는지 기록되어 있다.
하지만 상한 우유를 먹고 품평회가 끝날 때까지 배 아픔을 호소하지 않았다가, 그 후에 증상을 보인 사람에 대한 기록은 없기 때문에,
어떤 우유가 상한 우유였는지에 대해서는 확실히 알 수 없다.
농부 반디는 최악의 경우에 필요한 약의 개수를 구하려고 한다. 이를 구하는 프로그램을 구하여라.
입력
첫 줄에 정수 N, M, D, 그리고 S가 공백을 사이에 두고 주어진다. N은 친구들의 수, M은 우유의 수, D는 품평회 중 우유를 마신 이벤트의 수, S는 품평회 중 배 아픔을 호소한 사람의 수이다.
다음 D줄에 걸쳐, p, m, t가 공백을 사이에 두고 주어진다. 이는 친구 p가, m번 우유를, 품평회 시작 t분 후에 마셨다는 의미이다.
다음 S줄에 걸쳐, q, s가 공백을 사이에 두고 주어진다. 이는 친구 q가 품평회 시작 s분 후에 배 아픔을 호소했다는 의미이다. (1<=N<=50, 1<=M<=50, 1<=D<=1,000, 1<=S<=N, 1<=p, q<=N, 1<= m<=M, 1<=t, s<=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
1번 우유가 상함: 친구 1이 1분에 1번 우유를 마시고, 3분에 아프기 시작했고, 친구 2가 5분에 1번 우유를 마시고, 8분에 아프기 시작했기 때문에, 1번 우유는 상한 우유일 가능성이 있다. 이 경우, 친구 3도 이 품평회에서 우유를 마셨으므로, 품평회 후에 배가 아팠을 것이다. 따라서 이 경우 3개의 약을 준비해야 한다.
2번 우유가 상함: 친구 1이 2분에 2번 우유를 마시고, 3분에 아프기 시작했고, 친구 2가 7분에 2번 우유를 마시고, 8분에 아프기 시작했으므로, 2번 우유는 상한 우유일 가능성이 있다. 이 경우 친구 3은 2번 우유를 마신 적이 없으므로, 2개의 약을 준비해야 한다.
3번 우유가 상함: 3번 우유는 친구 2가 마신 적이 없는데 8분에 아팠으므로, 상한 우유일 수 없다. 뿐만 아니라, 친구 1이 4분에 마셨는데, 마시기 전인 3분에 배가 아팠으므로, 상한 우유일 수 없다.
4번 우유가 상함: 4번 우유는 친구 1이 1분에 마시고 3분에 아팠으므로, 이것만 보면 상한 우유일 가능성이 있다. 그러나 친구 2가 마신 적이 없는데 아팠으므로, 상한 우유일 가능성이 없다. 따라서 준비해야 할 약의 개수의 최댓값은 3이다.
로그인해야 코드를 작성할 수 있어요.