문제

지현이는 충남대학교 알고리즘 동아리 ANA에서 $N$명의 부원을 대상으로 $M$종류의 음료 시음회를 열었다 ($1 \le N, M \le 50$). 안타깝게도 준비한 $M$종류의 음료 중 정확히 하나가 상했다. 지현이는 어떤 음료가 상했는지 아직 모른다. 상한 음료를 마신 사람은 시음회 도중이나 그 이후에 아프게 된다.

지현이는 누가 어떤 음료를 언제 마셨는지, 그리고 누가 언제 아프기 시작했는지에 대한 기록을 가지고 있다. 이 정보를 바탕으로 어떤 음료가 상했을 가능성이 있는지 유추할 수 있다. 지현이는 상한 음료를 마시고 아픈 모든 사람을 치료하기 위해 필요한 약을 미리 준비하려고 한다. 어떤 음료가 상했더라도 아픈 모든 부원을 확실히 치료할 수 있도록 보장하기 위해 지현이가 준비해야 하는 약의 최소 개수를 구하시오.

입력

첫째 줄에 네 정수 $N, M, D, S$가 공백으로 구분되어 주어진다.

다음 $D$개의 줄($1 \le D \le 1\,000$)에는 각 줄에 세 정수 $p, m, t$가 주어진다. 이는 부원 $p$가 음료 $m$을 시간 $t$에 마셨음을 의미한다. ($1 \le p \le N; 1 \le m \le M; 1 \le t \le 100$) 한 부원이 같은 음료를 여러 번 마실 수 있으며, 같은 시간에 여러 종류의 음료를 마실 수도 있다.

다음 $S$개의 줄($1 \le S \le N$)에는 각 줄에 두 정수 $p, t$가 주어진다. 이는 부원 $p$가 시간 $t$에 아프기 시작했음을 의미한다. ($1 \le p \le N; 1 \le t \le 100$) 각 부원은 최대 한 번만 아프며, 상한 음료를 아프기 시작한 시간보다 엄격히 이전에 마셨을 때만 아프게 된다.

출력

어떤 음료가 상했더라도 아픈 사람들을 모두 치료할 수 있도록 지현이가 준비해야 하는 약의 최소 개수를 출력한다.

예제 입력 1

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

예제 출력 1

3