URI Online Judge | 1409

Zak Galou

By Alessandro de Luna Almeida Brazil
Timelimit: 4

Zak Galou is a famous wizard that kills monsters. The legend says that there is a hidden cave on the jungle confines that contains a millennial treasure. Until today, no adventurer managed to recover the treasure, because it is well guarded by terrible monsters. But Zak Galou is not an ordinary adventurer, and decided to prepare himself to recover the dreamed treasure.

Zak Galou features a certain amount of mana (a sort of magical energy) and a list of M spells. Each monster has a determined number of life points. Each time that Zak Galou casts a spell against a monster, Zak spends a certain amount of mana (the spell’s cost) and inflicts a certain amount of damage to the monster. The inflicted damage leads to a loss of life points from the monster (the number of life points loss depends on the spell). A monster is dead if he has zero or less life points. Zak always fights against one monster at a time. As a powerful wizard, he can cast the same spell several times, since he has enough amount of mana.

In his researches, Zak Galou found the treasure map. The cave is represented as a set of halls connected by galleries. The halls are identified sequentially from 1 to N. Zak always starts on the hall 1, and the treasure is always on the hall N. There are K monsters identified sequentially from 1 to K. Each monster lives inside a hall, from which he doesn’t leave (notice that is possible that more than one monster live on the same hall). During the search for the treasure, Zak Galou can only come out or recover a treasure from a hall if the hall is empty (with no monster). In other words, Zak must always, before leaves or recover the treasure from a hall, kill the monster(s) that lives in there.

Given the description of the spells, the monster and the cave, your task is to determine the minimum amount of initial mana necessary so Zak Galou can recover the treasure.

Input

The input contains several test cases. The first line of each test case contains four integers M, N, G and K, indicating respectively the number of spells (1 ≤ M ≤ 1000), of halls (1 ≤ N ≤ 1000), of galleries (0 ≤ G ≤ 1000000) and of monsters (0 ≤ K ≤ 1000).

Each one of the following M lines describes one spell. The description of a spell contains two integer numbers, the amount of consumed mana (between 1 and 1000) and the number of inflicted damage points (also between 1 and 1000).

Next, there are G lines, each one describing a gallery. A gallery is described by two integers numbers A and B (A ≠ B), representing the halls that the gallery connects. Zak can use the gallery on both ways, in other words, to go from A to B or from B to A.

Finally, the last K lines of a test case describe the monsters. The description of a monster contains two integers numbers representing respectively the hall on which he lives (between 1 and N inclusive), and your initial number of life points (between 1 and 1000 inclusive).

The final input is indicated by M = N = G = K = 0.

Output

For each input test case, your program must produce one output line, containing an integer number, the minimum amount of initial necessary mana. In case that is not possible to recover the treasure, you must print -1.

Sample Input Sample Output

3 4 4 2
7 10
13 20
25 50
1 2
2 4
1 3
3 4
2 125
3 160
3 4 4 1
7 10
13 20
25 50
1 2
2 4
1 3
3 4
2 125
1 3 1 1
1000 1000
1 2
3 1000
0 0 0 0

70
0
-1