SPOJ Brasil

Zak Galou é um famoso bruxo matador de monstros. Diz a lenda que existe uma caverna escondida nos confins da selva contendo um tesouro milenar. Até hoje nenhum aventureiro conseguiu recuperar o tesouro, pois ele é bem guardado por terríveis monstros. Mas Zak Galou não é um aventureiro qualquer e decidiu preparar-se para recuperar o tão sonhado tesouro.

Zak Galou dispõe de uma certa quantidade de mana (uma espécie de energia mágica) e de uma lista de M magias. Cada monstro tem um determinado número de pontos de vida. Cada vez que Zak Galou lança uma magia contra um monstro, Zak gasta uma certa quantidade de mana (o custo da magia) e inflinge um certo dano ao monstro. O dano inflingido provoca a perda de pontos de vida do monstro (o número de pontos perdidos depende da magia). Um monstro está morto se tiver zero ou menos pontos de vida. Zak sempre luta contra um monstro a cada vez. Como é um bruxo poderoso, ele pode usar a mesma magia várias vezes, desde que possua a quantidade necessária de mana.

Em suas pesquisas, Zak Galou conseguiu o mapa do tesouro. A caverna é representada como um conjunto de salões conectados por galerias. Os salões são identificados sequencialmente de 1 a N. Zak sempre inicia no salão 1 e o tesouro está sempre no salão N. Existem K monstros identificados seqüencialmente de 1 a K. Cada monstro vive em um salão, do qual não sai (note que é possível que mais de um monstro viva no mesmo salão). Durante a busca pelo tesouro, Zak Galou pode sair ou recuperar o tesouro de um salão somente se o salão estiver vazio (sem monstro). Em outras palavras, Zak deve sempre, antes de sair ou de recuperar o tesouro de um salão, matar o(s) monstro(s) que lá viver(em).

Dadas as descrições das magias, dos monstros e da caverna, sua tarefa é determinar a quantidade mínima inicial de mana necessária para que Zak Galou consiga recuperar o tesouro.

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém quatro inteiros M, N, G e K, indicando respectivamente o número de magias (1 ≤ M ≤ 1.000), de salões (1 ≤ N ≤ 1.000), de galerias (0 ≤ G ≤ 1.000.000) e de monstros (0 ≤ K ≤ 1.000).

Cada uma das M linhas seguintes descreve uma magia. A descrição de uma magia contém dois números inteiros, a quantidade de mana consumida (entre 1 e 1.000) e o número de pontos de danos provocados (também entre 1 e 1.000).

Em seguida, há G linhas, cada uma descrevendo uma galeria. Uma galeria é descrita por dois números inteiros A e B (A ≠ B), representando os salões que a galeria conecta. Zak pode utilizar a galeria nos dois sentidos, ou seja, para ir de A para B ou de B para A.

Finalmente, as últimas K linhas de um caso de teste descrevem os monstros. A descrição de um monstro contém dois números inteiros representando respectivamente o salão no qual ele vive (entre 1 e N inclusive) e o seu número inicial de pontos de vida (entre 1 e 1.000 inclusive).

O final da entrada é indicado por M = N = G = K = 0.

A entrada deve ser lida da entrada padrão.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma linha na saída contendo um número inteiro, a quantidade mínima inicial de mana necessária. Caso não seja possível recuperar o tesouro, você deve imprimir -1.

A saída deve ser escrita na saída padrão.

Exemplo

Entrada:
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

Saída:
70
0
-1