output_description: Print the minimum cost required to unlock all the treasure boxes. If it is
  impossible to unlock all of them, print -1.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      a_1 b_1
      c_{11} c_{12} ... c_{1{b_1}}
      :
      a_M b_M
      c_{M1} c_{M2} ... c_{M{b_M}}
attempt: # 142e'' (高速化)
  N, M = map(int, input().split())  # N<=12,M<=10**3
  
  openable_box_and_price = {}  # 開けられる箱のtaple:値段 なdict
  
  # 同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
  for i in range(M):  # 10**3
      a, b = map(int, input().split())
      c = tuple(map(int, input().split()))
  
      # print(c,":",a)
  
      if c in openable_box_and_price:
          # print("重複")
          if openable_box_and_price[c] > a:
              # print("安値更新")
              openable_box_and_price[c] = a
      else:
          openable_box_and_price[c] = a
  
  # 鍵に番号(0～)を付けるためlist化
  key_price = list(openable_box_and_price.values())
  key_openable_box = list(openable_box_and_price.keys())
  
  # ある箱を開けられる鍵のリストを作る
  box_and_openable_key = [[] for _ in range(N)]
  key_number = 0
  
  # for openable_boxes in key_openable_box:  #10**3
  openable_boxes = [openable_boxes for openable_boxes in key_openable_box]
  for openable_box in openable_boxes:  # 12
      box_and_openable_key[openable_box - 1].append(key_number)
      key_number += 1
  
  # print("########################")
  # print(key_price)
  # print(key_openable_box)
  # print(box_and_openable_key)
  # print("########################")
  
  # そもそも開けられる鍵が無い箱があったら-1を出力
  for openable_key in box_and_openable_key:
      if not openable_key:
          print(-1)
          break
  else:
      # すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
      cheapest_price = sum(key_price)  # 仮として最高値(全ての鍵を用いた場合)を入れる。
      keys_and_sum_price = {}  # 高速化のためにメモする
      key_combination = []
      base_key_combination = []
      # key_combination_append = base_key_combination.append #appendを外に出して高速化
      # key_combination_pop = key_combination.pop #popを外に出して高速化
  
      def get_price_of_cheap_key_combination(box_number, cheapest_price, key_combination):
          # print("箱:",box_number)
          base_key_combination = key_combination
  
          for openable_key in box_and_openable_key[box_number]:
  
              # 箱に対する鍵を追加する
              key_combination = base_key_combination + [openable_key]
              # print(key_combination,":",end="")
  
              # 値段を見る…dictにあったら省略
              tuple_key_combination = tuple(set(key_combination))
  
              if tuple_key_combination not in keys_and_sum_price:
                  # print("新規計算")
                  if base_key_combination != []:
                      now_price = (
                          keys_and_sum_price[tuple(set(base_key_combination))]
                          + key_price[openable_key]
                      )  # sum(key_price[i] for i in tuple_key_combination) #重複していなければ新しいのはopenable_key
                  else:
                      now_price = key_price[openable_key]
  
                  keys_and_sum_price[tuple_key_combination] = now_price
              else:
                  # print("重複")
                  now_price = keys_and_sum_price[tuple_key_combination]
  
              # print(now_price,",",cheapest_price)
              # 既に高かったら、そこで枝刈り
  
              if now_price < cheapest_price:
                  # 全部の箱に対して鍵を選択済みか
                  if box_number == N - 1:  # Yes→価格比較
                      # print("堀り終了")
                      # print("最安値更新:",now_price)
                      cheapest_price = now_price
                  else:  # No→再帰する
                      # print("深堀り")
                      cheapest_price = get_price_of_cheap_key_combination(
                          box_number + 1, cheapest_price, key_combination
                      )
              # else:
              # print("枝刈り")
  
              # key_combination_pop(-1)
  
          return cheapest_price
  
      print(get_price_of_cheap_key_combination(0, cheapest_price, key_combination))
  
problem_description: Statement
  
  We have N locked treasure boxes, numbered 1 to N.
  
  A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan),
  and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each
  key purchased can be used any number of times.
  
  Find the minimum cost required to unlock all the treasure boxes. If it is
  impossible to unlock all of them, print -1.
samples: [{"input": "2 3\n    10 1\n    1\n    15 1\n    2\n    30 2\n    1 2", "output": "25\n    \n\nWe can unlock all the boxes by purchasing the first and second keys, at the\ncost of 25 yen, which is the minimum cost required.\n\n* * *"}, {"input": "12 1\n    100000 1\n    2", "output": "-1\n    \n\nWe cannot unlock all the boxes.\n\n* * *"}, {"input": "4 6\n    67786 3\n    1 3 4\n    3497 1\n    2\n    44908 3\n    2 3 4\n    2156 3\n    2 3 4\n    26230 1\n    2\n    86918 1\n    3", "output": "69942"}]