행복 꾸러미

밥의 제과점이 문을 열었다. 손님이 모든 디저트를 맛보도록 여러 디저트를 하나로 묶어 파는 "행복 꾸러미" 행사를 한다.

예를 들어 초콜릿 케이크 꾸러미에는 초콜릿 레이어 케이크와 블랙 포레스트 케이크가 들어 있고 값은 20달러다. 과일 케이크 꾸러미에는 레몬 파운드 케이크와 키라임 케이크가 들어 있고 역시 20달러다. 이 네 가지를 한 조각씩 모두 담은 더 큰 꾸러미는 38달러라서 작은 꾸러미 두 개를 사는 것보다 싸다.

제과점이 파는 디저트를 종류마다 하나 이상 맛보려고 한다. 그래서 꾸러미를 몇 개 사야 하고, 쓰는 돈은 최소로 줄이려 한다.

꾸러미 구성에는 다음 성질이 있다.

• 임의의 두 꾸러미 $A$와 $B$에 대해 $A$의 디저트가 모두 $B$에도 들어 있거나, $B$의 디저트가 모두 $A$에도 들어 있거나, 두 꾸러미에 함께 들어 있는 디저트가 하나도 없다.
• 디저트를 하나만 사는 방법은 크기가 1인 꾸러미를 사는 것뿐이다. 모든 디저트에 그런 꾸러미가 있지는 않다.
• 가격은 정돈되어 있지 않다. 꾸러미 $B$에 든 디저트를 $B$ 자체를 사는 대신 다른 꾸러미 몇 개를 조합해서 더 싸게 모을 수도 있다.

첫 줄에 테스트 케이스 수 $T$가 주어진다 ($1 \le T \le 50$). 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $m$이 주어진다. $n$은 제과점이 파는 디저트 종류 수, $m$은 꾸러미 수다 ($1 \le n \le 100$, $1 \le m \le 150$).

이어지는 $m$개의 줄에 꾸러미가 하나씩 주어진다. $i$번째 줄은 두 정수 $p_i$와 $s_i$로 시작한다. $p_i$는 꾸러미 $i$의 가격이고 ($0 < p_i \le 10^6$), $s_i$는 꾸러미에 든 디저트 개수다 ($1 \le s_i \le n$). 줄의 나머지에는 $1$ 이상 $n$ 이하의 서로 다른 정수 $s_i$개가 오고, 꾸러미에 들어 있는 디저트를 뜻한다.

$n$가지 디저트는 모두 적어도 한 꾸러미에 들어 있다.

각 테스트 케이스마다 모든 디저트를 하나 이상씩 얻는 데 드는 최소 비용을 한 줄에 출력한다. 이 값은 32비트 부호 있는 정수 범위에 들어간다.