Problema de Compras em Espaçoloja: Maximização de Valor

Algoritmo 5 Espaçoloja Expert Tempo máximo de execução 1s DESCRIÇÃO Descrição Oto precisa comprar mantimentos para sua viagem mas além de não ter muito dinheiro sua nave também não foi projetada para longas viagens por isso existem algumas restrições sobre o que ele pode comprar A comida para viagens espaciais por exemplo só é vendida em grandes pacotes porém o dispositivo de armazenamento de comida é relativamente pequeno e não comporta mais que um pacote Por causa dessas restrições Oto decidiu fazer uma lista dos produtos que poderia encontrar e atribuir um valor de acordo com suas necessidades para cada um desses produtos bem como fazer uma lista dos produtos que ele não poderia comprar ao mesmo tempo por causa das restrições de sua nave Deste modo de acordo com a lógica de Oto comida água e combustível teriam um valor altíssimo enquanto roupas teriam um valor bem mais baixo por exemplo afinal é possível sobreviver usando aqueles trapos por mais um tempo mas ele não vai a lugar algum sem os outros três itens Agora que ele chegou em uma espaçoloja ele sabe o preço de cada item e precisa decidir quais itens de sua lista comprar de modo que suas compras lhe tragam o máximo de valor possível Formato de entrada A primeira linha da entrada é dada por dois números inteiros positivos N 1 N 1000 e D 1 D 107 indicando o número de itens na lista de Oto e quanto de dinheiro ele possui A seguir são apresentadas N linhas contendo dois números inteiros v e p cada uma onde o primeiro indica o valor daquele item para Oto 1 v 1000 e a segunda indica o preço do item na espaçoloja 1 p 107 Depois é apresentada uma linha com um único número inteiro nãonegativo M indicando o número de incompatibilidades entre os itens seguido por M linhas contendo dois números inteiros positivos i e j 1 i j N indicando que o iésimo e o jésimo itens são incompatíveis devido as restrições da nave e por isso não podem ser comprados juntos Formato de saída A saída será dada por um único número V indicando o maior valor que ele consegue obter de suas compras Exemplos de Entrada 7 20 3 5 2 6 4 8 5 10 10 15 7 9 6 4 2 5 7 1 5 Saída 16 Entrada 5 17 2 6 4 10 5 8 2 3 3 7 2 1 4 2 3 Saída 8