Infinity Quest

O MMO Infinity Quest oferece, em datas festivas e ocasiões especiais, uma série de $N$ quests extras diárias, onde o jogador pode coletar gemas, experiência e equipamentos raros.

Algumas destas quests podem ter, como pré-requisito, algumas destas quests extras, mas como elas se repetem de tempos em tempos, os jogadores podem ter ou não tais requisitos já atendidos. Além disso, para poder ingressar em uma quest extra é preciso pagar uma certa quantia de moedas de ouro, item raro do jogo.

Dada a relação das quests extra, a quantidade de ouro a ser paga por cada uma, a premiação, em termos de pontos de experiência, e a relação de pré-requisitos, determine o maior número de pontos de experiência que um dado jogador pode obter, conhecidas as quests que ele já cumpriu e quantidade de moedas de ouro que possui.

Considere que um jogador pode cumprir novamente uma quest que já cumpriu antes e assuma que o jogador complete, com sucesso, qualquer quest que ele ingresse, recebendo a totalidade dos pontos de experiência que a quest oferece. Não devem ser contabilizados os pontos referentes à quests já cumpridas anteriormente pelo jogador.

Entrada

A primeira linha da entrada contém o número $N$ $(1\leq N\leq 10)$ de quests extra diárias.

Cada uma das $N$ linhas seguintes contém o título da quest (uma string de, no máximo, 50 caracteres alfabéticos, maiúsculos e minúsculos, sem acentos), o número $G$ $(1\leq G\leq 5)$ de moedas de ouro necessárias para ingressar na quest e o número $X$ $(1\leq X\leq 10^8)$ de pontos de experiência que o jogador é recompensado por cumprir a quest. Estas informações estão separadas por um espaço em branco.

Em seguida, há mais $N$ linhas contendo as informações de pré-requisitos das quests: primeiro é dado o título de uma das quests, em seguida o número $P$ $(0\leq P\leq 5)$ de pré-requisitos da quest e os $P$ títulos das quests que devem ter sido cumpridas (em qualquer ordem) para que esta quest seja destravada. Não haverão requisitos circulares ( $A$ depende de $B$ que depende de $A$ ).

Por fim, há duas linhas: primeira contém o número $C$ ( $1\leq C\leq 30$ ) de moedas de ouro que o jogador possui; a segunda contém o número $Q$ $(0\leq Q\leq N)$ de quests extras que o jogador já cumpriu previamente, seguido dos títulos destas referidas quests, separados por espaços em branco.

Saída

Imprima, em uma linha, o máximo de pontos de experiência que o jogador pode obter no novo ciclo de $N$ quests extras diárias.

Exemplo de entrada 1

3
Festival 2 140
Carnival 2 160
Birthday 2 180
Festival 0
Carnival 0
Birthday 0
5
0

Exemplo de saída 1

Explicação do exemplo 1: No primeiro caso, nenhuma das três quests tem pré-requisitos. Assim o jogador pode, a princípio, escolher qualquer uma delas para cumprir. Porém ele tem apenas 5 moedas de ouro e cada quest exige 2 moedas para a participação. Assim o ideal é que ele cumpra as quests “Carnival” e “Birthday”, obtendo um total de $160 + 180 = 340$ pontos de experiência.

Exemplo de entrada 2

5
Hunting 3 200
Upgrading 2 150
Dungeon 1 80
Boss 2 170
Treasure 1 50
Hunting 0
Upgrading 1 Treasure
Dungeon 0
Boss 2 Upgrading Treasure
Treasure 0
6
1 Treasure

Exemplo de saída 2

Explicação do exemplo 2: No segundo caso, a melhor estratégia é a seguinte: como o jogador já cumpriu a questão “Treasue” em algum momento, ele pode cumprir a quest “Upgrading” e, com ambas completas, ele pode completar as próximas três quests (“Dungeon”, “Boss” e “Treasure”), totalizando 450 moedas de ouro. Observe que ele pode refazer a quest “Treasure”.