teddy online judge

94. Concurso Nacional de Ajedrez

Limite de tiempo : 3 seg.   Total runs : 26  Aceptados : 12

Hoy, además de ser el 10° Concurso Nacional de Programación, se celebra el 15° Concurso Nacional de Ajedrez. Tú y ocho amigos más (curiosamente, sus nombres equivalen a los números del 1 al 9) van a entrar representando al Instituto de Tecnologías del Centro (ITC). Tu delegación quiere ganar y te está pidiendo ayuda para lo mismo.

Este concurso está dividido en categorías, y cada miembro de la delegación puede participar en solo una de ellas, y en una categoría se deben inscribir exactamente tres miembros de una delegación. Afortunadamente hay muchísimas categorías (más de mil), así que hay para todos los gustos. El problema es que tus demás compañeros no tienen mucha confianza en ganar, así que se tienen que dar apoyo moral entre ellos mismos, inscribiéndose a la misma categoría juntos. Es más, conociendo quiénes se inscriben juntos a una categoría, puedes saber de antemano cuántos puntos van a ganar, pero si no están con los compañeros correctos, no van a ganar ningún punto.

Entrada

La primer línea de la entrada contiene un entero N_c (1 ≤ N_c ≤ 100), que contiene el número de casos de prueba. La primer línea de cada caso de prueba contiene un entero n (0 ≤ n ≤ 512), el número de equipos de los cuales puedes predecir su puntuación. Después vienen n líneas con cuatro enteros, a, b, c, p (1 ≤ a < b < c ≤ 9, 1 ≤ p ≤ 1000), siendo a,b,c los nombres de los miembros de tu delegación y p el puntaje que pueden obtener entre los tres si se inscriben a la misma categoría. Se garantiza que cada equipo posible aparecerá a lo mucho una vez en la entrada.

Salida

Para cada caso de prueba, imprime una línea con el número del caso, seguido un entero que represente el máximo puntaje que pueden obtener entre todos. Sigue el formato de ejemplo.

Entrada/Salida de ejemplo

3
2
1 2 4 100
1 5 9 1000
0
3
1 2 3 1
4 5 6 2
7 8 9 4

Caso 1: 1000
Caso 2: 0
Caso 3: 7