메리 크리스마스

문제

국제 크리스마스 선물 회사(ICPC)는 산타를 고용해서 크리스마스에 선물을 배달하는 회사다. 많은 부모가 12월 24일의 정해진 시각에 아이에게 선물을 배달해 달라고 ICPC에 요청한다. 산타 한 명이 선물 두 개 이상을 배달할 수 있지만, 집 사이를 이동하는 데 시간이 걸리므로 모든 요청을 제시간에 끝내려면 산타가 두 명 이상 필요할 수도 있다.

산타를 고용하는 데는 돈이 많이 든다. 그래서 ICPC 사장은 배달 일정을 최적화하려고 뛰어난 프로그래머인 당신을 고용했다. 주어진 요청을 모두 제시간에 끝내는 데 필요한 산타의 최소 인원을 구하는 프로그램을 작성하라. 산타는 모두 훈련이 잘 되어 있어서 마을 어디에나 숨어 있을 수 있으므로, 각 산타의 처음 위치는 마음대로 정할 수 있다.

입력

입력은 데이터 세트 여러 개로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N M L
u1 v1 d1
u2 v2 d2
...
uM vM dM
p1 t1
p2 t2
...
pL tL

각 데이터 세트의 첫 줄에는 정수 세 개 $N$ , $M$ , $L$ ( $1 \le N \le 100$ , $0 \le M \le 1000$ , $1 \le L \le 1000$ )이 주어진다. 차례로 집의 수, 도로의 수, 요청의 수다.

이어지는 $M$ 개의 줄은 도로망을 나타낸다. $i$ 번째 줄에는 정수 세 개 $u_i$ , $v_i$ , $d_i$ ( $0 \le u_i < v_i \le N - 1$ , $1 \le d_i \le 100$ )가 주어진다. 집 $u_i$ 와 집 $v_i$ 를 잇는 길이 $d_i$ 인 도로가 있다는 뜻이다. 도로는 모두 양방향이다. 같은 집 쌍을 잇는 도로는 많아야 하나다. 도로망 전체가 연결되어 있지 않을 수도 있다.

다음 $L$ 개의 줄은 요청을 나타낸다. $i$ 번째 줄에는 정수 두 개 $p_i$ , $t_i$ ( $0 \le p_i \le N - 1$ , $0 \le t_i \le 10^8$ )가 주어진다. 시각 $t_i$ 에 집 $p_i$ 로 선물을 배달해 달라는 요청이 있다는 뜻이다. 장소와 시각이 모두 같은 요청은 많아야 하나다. 이동 외에 걸리는 시간은 무시해도 되고, 산타의 속도는 모두 같아서 단위 시간에 단위 거리를 이동한다.

입력의 끝은 공백으로 구분한 0 세 개만 있는 줄로 표시한다. 이 줄은 데이터 세트로 처리하지 않는다.

출력

데이터 세트마다 모든 요청을 제시간에 끝내는 데 필요한 산타의 최소 인원을 한 줄에 출력한다.