1207 - Os Benefícios da Vodka

• ID: 1207
• IdBecrowd: 1207
• Tags: grafos
• Nível: 9
• Tempo Limite: 4 segundos
• Memória: 200 MB
• Categoria: Grafos
• Autor: Marcio T. I. Oshiro, Brasil

Descrição

São Peterburgo é conhecida como a capital da cerveja russa e abriga diversas cervejarias importantes. Dizem que a qualidade da água da cidade é responsável por uma cerveja de excelente qualidade. Além de fábricas tradicionais, como a Heineken, algumas marcas locais são destacadas, como a Tinkoff e a Baltika. Também na cidade são produzidas algumas das melhores vodkas do mundo. A mais antiga, chamada Liviz, data de 1897. Esta destilaria produz vodkas de  excelente qualidade, medida por padrões internacionais. Curiosamente, alguns tipos de vodkas, quando consumidos juntos, acabam tendo, segundo os  especialistas, sabor muito melhor. Dessa forma, alguns tipos de vodka são reunidos em categorias que, quando compradas totalmente pelo consumidor, trazem um benefício agregado medido segundo padrões internacionais de qualidade. Cada uma das vodkas tem um preço associado, e sua tarefa é encontrar uma compra que maximize o benefício total menos o custo das vodkas adquiridas.

Reescrevendo, cada vodka tem um custo Cj e existem M categorias diferentes, cada qual com um benefício Bi. Um benefício só é computado se todos os tipos de vodka que compõem a categoria são adquiridos. Uma mesma garrafa de vodka pode participar de mais de uma categoria para computar o benefício. Sua tarefa é determinar quais tipos de vodka comprar de forma a maximizar a soma dos benefícios adquiridos menos o custo dos itens  comprados. Você pode supor que foi à Russia com dinheiro suficiente para comprar todos os tipos de vodka produzidos pela Liviz (oba!! :D).

Entrada

A entrada é composta por diversas instâncias e termina com final de arquivo (EOF). A primeira linha de cada instância contém dois inteiros N (1 ≤ N ≤ 600) e M (1 ≤ M ≤ 400) representando, respectivamente, a quantidade de tipos diferentes de vodka a venda e o número de categorias existentes. Os tipos de vodka são identificados por números de 1 a N e as categorias por números de 1 a M .

A linha seguinte contém N inteiros, C j (1 ≤ C j ≤ 1000) para (1 ≤ j ≤ N ), separados por espaço, correspondendo ao custo da vodka j . Na próxima linha existem M inteiros, P i (1 ≤ P i ≤ N ) para (1 ≤ i ≤ M ), separados por espaço, indicando quantos tipos diferentes de vodkas compõe a categoria i . Cada uma das M linhas seguintes descreve uma categoria começando com um inteiro, B i (1 ≤ B i ≤ 1000) para (1 ≤ i ≤ M ), indicando seu benefício, seguido pelos tipos de vodka que a compõe, separados por espaços.

Saída

Para cada instância imprima, em uma única linha, o maior valor que pode ser obtido da soma dos benefícios das categorias adquiridas menos o custo dos tipos de vodkas compradas.

Exemplos

Exemplo de Entrada

2 3

                                80 80

                                1 2 1

                                90 1

                                50 1 2

                                25 2

                                4 3

                                50 200 50 130

                                2 2 2

                                70 1 2

                                260 2 3

                                120 3 4

Exemplo de Saída

10

                                30