상한 우유

농부 존은 자기 농장에서 나오는 우유의 품질로 널리 알려져 있다. 오늘 존은 가장 친한 친구 $N$명($1 \le N \le 50$)을 불러 우유 시음회를 연다. 시음회에 내놓은 우유는 $M$종류($1 \le M \le 50$)이고, 그중 정확히 한 종류가 상했다. 어느 것이 상했는지는 존도 모른다. 상한 우유를 마신 사람은 시음회 도중이든 끝난 뒤든 언젠가 병이 난다.

시음회 기록이 주어진다. 누가 언제 어떤 우유를 마셨는지, 그리고 누가 언제 병이 났는지가 적혀 있다. 이 기록으로 어떤 우유가 상한 우유일 수 있는지 추려낼 수 있다. 어떤 우유가 상했더라도 병이 난 사람을 모두 치료할 수 있도록, 존이 준비해야 하는 약의 최소 개수를 구하라. 시음회가 끝난 뒤에 병이 나는 사람도 치료 대상이다.

첫째 줄에 정수 $N$, $M$, $D$, $S$가 주어진다.

다음 $D$개 줄($1 \le D \le 1000$)에는 각각 세 정수 $p$, $m$, $t$가 주어진다. 사람 $p$가 시각 $t$에 우유 $m$을 마셨다는 뜻이다. $p$는 $1$ 이상 $N$ 이하, $m$은 $1$ 이상 $M$ 이하, $t$는 $1$ 이상 $100$ 이하이다. 한 사람이 같은 우유를 여러 번 마실 수도 있고, 같은 시각에 여러 종류의 우유를 마실 수도 있다.

다음 $S$개 줄($1 \le S \le N$)에는 각각 두 정수 $p$, $t$가 주어진다. 사람 $p$가 시각 $t$에 병이 났다는 뜻이다. $p$는 $1$ 이상 $N$ 이하, $t$는 $1$ 이상 $100$ 이하이다. 한 사람은 많아야 한 번 병이 나고, 병이 난 이유는 시각 $t$보다 엄밀히 앞선 시각에 상한 우유를 마셨기 때문이다.

시음회 도중과 그 뒤에 병이 나는 사람을 모두 치료할 수 있도록 존이 준비해야 하는 약의 최소 개수를 한 줄에 출력한다.

사람은 3명이고 우유는 4종류이다. 사람 1은 시각 3에, 사람 2는 시각 8에 병이 났다. 사람 3은 시음회 도중에는 병이 나지 않았지만 끝난 뒤에 병이 날 가능성은 남아 있다. 우유를 한 종류씩 따져 보자. 병이 난 사람이 모두 병이 나기 전에 그 우유를 마셨다면, 그 우유는 상한 우유일 수 있다.

우유 1: 병이 난 사람 1과 2가 모두 병이 나기 전에 마셨으므로 상한 우유일 수 있다. 이 경우 사람 3도 마셨으므로 모두 3명이 병이 난다. 사람 3은 시음회가 끝난 뒤에 병이 난다.

우유 2: 병이 난 두 사람이 모두 병이 나기 전에 마셨으므로 이것도 상한 우유일 수 있다. 다른 사람은 마시지 않았으므로 최악의 경우에도 2명만 병이 난다.

우유 3: 사람 1이 병이 나기 전에 마시지 않았으므로 상한 우유가 아니다. 사람 1은 시각 4에 마셨고 시각 3에 병이 났다. 우유 3이 원인이 되려면 늦어도 시각 2까지는 마셨어야 한다.

우유 4: 사람 2는 마시지 않았는데도 병이 났으므로 상한 우유가 아니다.

우유 1이 상했다면 3명을 치료해야 하므로 답은 3이다.