SPOJ Brasil

A Polícia Montada Real Canadense (Royal Canadian Mounted Police) é uma instituição muito famosa, cujas origens remontam ao século XIX. Sua tarefa é levar a lei aos locais mais longínquos do país continental. Hoje a polícia montada tem um efetivo de 25000 homens e cerca de 5000 cavalos.

Cada sede da RCMP tem um haras em que os animais são muito bem cuidados, e designados aos policiais com quem têm mais afinidade. Esta afinidade é inferida em observações dos oficiais com vários anos de experiência, observando os policiais montando os animais disponíveis. No Fairmont Banff Springs Haras, onde ficam os cavalos montados pelos policiais da região de Banff Springs, é necessário resolver o problema de decidir quais soldados montarão quais cavalos. Note que um cavalo pode ser montado por vários policiais, mas um policial só monta um determinado cavalo. Cada cavalo tem um limite de policiais que podem montá-lo. Ou seja, de posse da afinidade dos vários policiais com os animais que montou nos últimos tempos, deseja-se encontrar uma atribuição dos cavalos aos vários policiais, de tal forma que o maior número possível de policiais tenham um cavalo para montar.

Entrada

A entrada é composta de diversas instâncias. A primeira linha de cada instância consiste em três inteiros n (1 <= n <= 100), m (1 <= m <= 100) e k (1 <= k <= 1000) indicando o número de cavalos, o número de soldados e o número de afinidades. A linha seguinte contêm n inteiros c1,c2,..,cn indicando que no i-ésimo cavalo pode montar ci (1 <= ci <= 100) soldados. Nas k linhas seguintes temos dois inteiros u (1 <= u <= n) e v (1 <= v <= m) indicando que existe afinidade entre o cavalo u e o soldado v.

A entrada termina com final de arquivo.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima o número máximo de policiais que podem ter um cavalo para montar em uma atribuição.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada:
5 3 7
1 1 1 1 1
1 1
1 2
2 1
2 2
2 3
4 3
5 3

Saída:
Instancia 1
3