Duelo

---

Descrição

Autor: Daniel "Pufe" Ribeiro

A bebida favorita do Lucas Aquino é Duelo, que existe em muitos sabores distintos. Ele encontrou vários pacotes sortidos no supermercado e quer saber qual o jeito mais barato de comprar pelo menos um Duelo de cada sabor que tem no mercado.

---

Entrada

A entrada é composta de vários casos de teste, a primeira linha da entrada contém um inteiro T que indica quantos casos de teste seguirão. Cada caso de teste começa com um inteiro N indica quantos pacotes têm no supermercado. Seguem então N linhas descrevendo os pacotes. Uma linha descrevendo o pacote i começa com dois inteiros Pi e Qi que indicam respectivamente o preço do pacote e quantos Duelos ele tem. Seguem então Qi palavras que representam os sabores de Duelo naquele pacote.

---

Saída

Para cada caso de teste, imprima uma linha com um único número inteiro: o custo mínimo para comprar um Duelo de cada sabor.

 

Restrições

1 <= N,Q_i <= 16

1 <= Pi <= 10000

Cada nome de sabor de Duelo contém apenas letras minúsculas sem acentos.

 

Exemplos de Entrada	Exemplos de Saída
Copiar! 3 1 2 1 morango 3 3 2 morango limao 5 3 morango acai limao 3 2 acai limao 2 4 2 coco cacau 3 1 blueberry	Copiar! 2 5 7