XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: saco.x, onde x deve ser c, cpp, java, js ou py

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 grupo A 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 ≤ N ≤ 30) que indica a quantidade de cidades. A segunda linha contém um inteiro T (10 ≤ T ≤ 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 XPCKV0V1...VK-1, onde X é um inteiro que representa a cidade (numeradas de 0 a N - 1); P é um inteiro (1 ≤ P ≤ 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 ≤ K < N ) que indica quantas rotas saem da cidade X; e cada Vi é 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 ij => Vi ≠ Vj.

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.

Exemplos

Entrada
4
20
0 9 A 2 1 2
1 8 B 1 2
2 7 A 1 3
3 6 B 1 1
			
Saída
1
			
Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação