Zak Galou

Zak Galou is a famous wizard who hunts monsters. Legend says a cave hidden deep in the jungle holds a treasure that is thousands of years old. No adventurer has recovered it, because terrible monsters guard it well. Zak Galou is not an ordinary adventurer, and he has started preparing to take the treasure.

Zak Galou has a certain amount of mana, a kind of magical energy, and a list of $M$ spells. Every monster has a fixed number of hit points. Each time Zak casts a spell at a monster, he spends the mana cost of that spell and deals the damage of that spell to the monster. A monster that takes damage loses that many hit points. A monster is dead once its hit points are $0$ or less. Zak always fights one monster at a time. He is a powerful wizard, so he can cast the same spell as many times as he wants while he still has the mana it needs.

His research got Zak Galou the treasure map. The cave is given as a set of rooms connected by galleries. The rooms are numbered from $1$ to $N$. Zak always starts in room $1$ and the treasure is always in room $N$. There are $K$ monsters, numbered from $1$ to $K$. Each monster lives in one room and never leaves it, and several monsters can live in the same room. Zak can leave a room, or pick up the treasure of a room, only while the room is empty, that is, while no monster is in it. In other words, before he leaves a room or takes the treasure of a room, he must kill every monster living there.

Given the spells, the monsters and the cave, work out the smallest amount of mana Zak Galou needs at the start to recover the treasure.

The input holds several test cases. The first line of each test case has four integers $M$, $N$, $G$ and $K$, in this order the number of spells ($1 \le M \le 1000$), of rooms ($1 \le N \le 1000$), of galleries ($0 \le G \le 1000000$) and of monsters ($0 \le K \le 1000$).

Each of the next $M$ lines describes one spell with two integers, the amount of mana it consumes (from $1$ to $1000$) and the damage it deals (also from $1$ to $1000$).

The next $G$ lines describe one gallery each with two integers $A$ and $B$ ($A \ne B$), the rooms that the gallery connects. Zak can use a gallery in both directions, so he can go from $A$ to $B$ and from $B$ to $A$.

The last $K$ lines of a test case describe one monster each with two integers, the room it lives in (from $1$ to $N$) and its initial number of hit points (from $1$ to $1000$).

The end of the input is marked by a line with $M = N = G = K = 0$, which is not processed.

For each test case print one line with one integer, the minimum initial amount of mana. If the treasure cannot be recovered, print -1.