Sacoleiro

Seu amigo sacoleiro pediu sua ajuda num problema que ele está enfrentando. Ele tem um mapa de cidades que ele já conhece e que são interessantes para ele, além das rotas entre as mesmas. Ele pretende fazer uma viagem para comprar presentes para seu filho e para sua filha. O problema é que nem todos os presentes têm o mesmo preço, alguns são obviamente mais caros que os outros, e ele não quer ser injusto dando presentes mais caros para um ou para outro. O objetivo é fazer com que diferença entre a soma dos valores dos presentes seja a menor possível (de preferência que sejam iguais, naturalmente). Há, também, um limite de quanto ele pode gastar na viagem.

O sacoleiro tem um mapa com N cidades e as rotas que as ligam. Além disso, cada cidade pertence ao grupo A ou ao grupo B. No grupoA estão as cidades em que há presentes para o filho, enquanto que no grupo B estão as cidades com presentes para a filha. Sempre que ele para numa cidade ele pode comprar ou não o presente, mesmo que ele já tenha estado lá antes, inclusive pode comprar mais de uma unidade do mesmo presente (enquanto tiver dinheiro disponível, naturalmente). As cidades são numeradas de 0 a N - 1. O trajeto deve sempre começa na cidade 0. O tamanho do percurso não importa para o sacoleiro. O total disponível de dinheiro para os presentes é T. O sacoleiro não pode terminar a viagem sem ter comprado pelo menos um presente para algum dos filhos.

Tarefa

Escreva um programa que, dadas N cidades, as rotas entre elas e os valores de presentes de cada cidade, retorne qual a diferença mínima possível entre a soma dos presentes do grupo A e a soma dos presentes do grupo B.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N (2 $\leq$ N $\leq$ 30) que indica a quantidade de cidades. A segunda linha contém um inteiro T (10 $\leq$ T $\leq$ 100) que indica a quantidade de dinheiro que o sacoleiro tem para gastar. As N linhas seguintes contêm a descrição cada cidade. Cada uma dessas linhas tem o formato XPCKV₀V₁...V_K-1, onde X é um inteiro que representa a cidade (numeradas de 0 a N - 1); P é um inteiro (1 $\leq$ P $\leq$ 10) que indica o valor do presente da cidade X; C é um caractere A ou B, indicando a que grupo a cidade X pertence; K é um inteiro (0 $\leq$ K $\leq$ N ) que indica quantas rotas saem da cidade X; e cada V_i é um inteiro indicando um dos possíveis destinos a partir da cidade X. Note que as rotas não são bidirecionais. Uma cidade nunca terá rota para ela mesma e pode-se assumir que i $\neq$ j => V_i $\neq$ V_j.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha com um inteiro representando a menor diferença possível de valores entre os presentes comprados para o grupo A e para o grupo B.

4
20
0 9 A 2 1 2
1 8 B 1 2
2 7 A 1 3
3 6 B 1 1