할인 패키지

Gigel은 요리 실력을 시험해 보려고 시장에 재료를 사러 간다. 시장에서는 $m$가지 종류의 물건을 $n$일 동안 할인 패키지로 판다. $i$번째 날에 Gigel은 그날 판매하는 할인 패키지를 사거나 사지 않을 수 있다. 할인 패키지는 $m$가지 물건 종류의 집합의 공집합이 아닌 부분집합으로 나타내며 가격이 정해져 있다.

$m$, $n$과 $n$개의 할인 패키지 각각의 가격과 구성을 알 때, $m$가지 종류의 물건을 각각 하나 이상 사기 위해 Gigel이 지불해야 하는 최소 금액을 구하라.

입력의 첫째 줄에는 두 수 $m$과 $n$이 주어진다.

다음 $n$개의 줄에는 $n$개의 할인 패키지가 설명된다. $(i+1)$번째 줄($1 \le i \le n$)에는 그날 할인 패키지에 들어 있는 물건의 수 $nr$과 가격 $p$가 주어진다. 이어서 같은 줄에 그 패키지에 들어 있는 물건의 번호 $nr$개가 주어진다.

모든 종류의 물건을 각각 하나 이상 사기 위해 지불해야 하는 최소 금액을 양의 정수로 출력한다.

• $1 \le m \le 17$, $1 \le n \le 1,000$, $1 \le p \le 1,000,000$
• 입력에 나오는 모든 수는 양의 정수이다.
• 할인 패키지는 통째로만 살 수 있다.
• 어떤 패키지를 나타내는 물건 번호는 집합 $\{1, 2, \dots, m\}$의 값을 가진다.
• 모든 테스트 케이스에 답이 존재함이 보장된다.

고른 패키지는 첫 번째와 세 번째이고, 최소 비용 $10 + 11 = 21$을 얻는다. Gigel은 종류 1의 물건 하나, 종류 2의 물건 하나, 종류 3의 물건 둘, 종류 4의 물건 하나, 종류 5의 물건 하나를 산다.