자크 갈루

자크 갈루는 몬스터를 사냥하는 이름난 마법사다. 정글 깊은 곳에 아주 오래된 보물이 잠들어 있는 동굴이 숨어 있다는 전설이 전해진다. 보물은 무서운 몬스터가 지키고 있어서 지금까지 어떤 모험가도 되찾지 못했다. 자크 갈루는 평범한 모험가가 아니어서, 그 보물을 손에 넣을 준비를 시작했다.

자크 갈루에게는 일정량의 마나(마법 에너지)와 마법 $M$개의 목록이 있다. 몬스터마다 체력이 정해져 있다. 자크가 몬스터에게 마법을 한 번 쓰면 그 마법의 비용만큼 마나를 소모하고 몬스터에게 그 마법의 피해량만큼 피해를 준다. 피해를 입은 몬스터는 그만큼 체력을 잃는다. 체력이 $0$ 이하가 된 몬스터는 죽는다. 자크는 항상 몬스터 한 마리와 차례로 싸운다. 강력한 마법사이므로 필요한 마나가 남아 있는 한 같은 마법을 몇 번이든 다시 쓸 수 있다.

자크 갈루는 조사 끝에 보물 지도를 얻었다. 동굴은 통로로 이어진 방의 집합으로 나타난다. 방에는 $1$번부터 $N$번까지 차례로 번호가 붙어 있다. 자크는 항상 $1$번 방에서 출발하고 보물은 항상 $N$번 방에 있다. 몬스터는 $K$마리이고 $1$번부터 $K$번까지 차례로 번호가 붙어 있다. 각 몬스터는 방 하나에 살면서 그 방을 벗어나지 않는다. 한 방에 몬스터가 여러 마리 사는 경우도 있다. 자크는 방이 비어 있을 때, 즉 그 방에 몬스터가 없을 때만 그 방에서 나갈 수 있고 그 방의 보물을 챙길 수 있다. 다시 말해 어떤 방에서 나가기 전에, 또는 그 방의 보물을 챙기기 전에 그 방에 사는 몬스터를 모두 죽여야 한다.

마법과 몬스터, 동굴의 정보가 주어진다. 자크 갈루가 보물을 되찾으려면 처음에 마나가 최소 얼마나 있어야 하는지 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 네 개 $M$, $N$, $G$, $K$가 주어진다. 차례로 마법의 수($1 \le M \le 1000$), 방의 수($1 \le N \le 1000$), 통로의 수($0 \le G \le 1000000$), 몬스터의 수($0 \le K \le 1000$)를 뜻한다.

이어지는 $M$개 줄에는 마법이 한 줄에 하나씩 주어진다. 각 줄에는 정수 두 개가 있고, 소모하는 마나의 양($1$ 이상 $1000$ 이하)과 주는 피해량($1$ 이상 $1000$ 이하)이다.

그다음 $G$개 줄에는 통로가 한 줄에 하나씩 주어진다. 각 줄에는 정수 $A$와 $B$($A \ne B$)가 있고, 그 통로가 잇는 두 방의 번호다. 자크는 통로를 양쪽 방향으로 지날 수 있다. 즉 $A$에서 $B$로 갈 수도 있고 $B$에서 $A$로 갈 수도 있다.

마지막 $K$개 줄에는 몬스터가 한 줄에 하나씩 주어진다. 각 줄에는 정수 두 개가 있고, 그 몬스터가 사는 방의 번호($1$ 이상 $N$ 이하)와 처음 체력($1$ 이상 $1000$ 이하)이다.

입력의 끝은 $M = N = G = K = 0$인 줄로 표시되고, 이 줄은 처리하지 않는다.

테스트 케이스마다 한 줄에 정수 하나를 출력한다. 처음에 필요한 마나의 최솟값이다. 보물을 되찾을 수 없으면 -1을 출력한다.