クイズ

あなたはクイズ番組のディレクターである． クイズ番組には解答者として N 人が出演予定であり，それぞれ 1 から N まで番号付けられている．

問題は M+1 問出題する予定であり，それぞれの問題は 1 から M+1 まで番号付けられている． 問題は番号順に出題され，それぞれ早押しで最初に正解した人にのみ得点が入る．i 問目の問題の得点は整数 S_i である． M+1 問目の問題を終えた時点で総合得点が最大の人が優勝する． ただし，最大得点の人が複数人存在する場合，優勝者は存在しない．

現在 M 問目まで配点を決めたので，M+1 問目の配点を決めようと考えている． 最後の問題は，誰でも逆転できる点数にするのがクイズ番組のお約束である． しかし，その場で解答者たちの総合得点を見て問題の点数を決めると，解答者たちのやる気を削ぐ可能性がある．そこで， どんな点数状況でも全員に逆転のチャンスがあるような点数設定をあらかじめ考えることにした．

幸い，1 から M 問目まではそれぞれ正解する可能性がある解答者が分かっている．M+1 問目は全員が正解する可能性のある問題である．正解する可能性がある解答者の中で，早押しで正解した1名のみが問題の得点 S_i を得る．問題への解答は正解した解答者が現れた時点で締め切られ，同じ解答者は何度でも解答を行うことができるため，ある問題の得点 S_i を誰も得られない場合は考慮しなくてよい．また，複数人の解答者がある問題の得点 S_i を重複して獲得したり，得点を分け合ったりすることもない．

各問の配点と正解可能な解答者の情報を基に， 起こりうるどのような得点状況においても，最後の問題を正解すれば必ず誰でも優勝できるように最後の問題の点数 S_M+1 を設定したい． 条件を満たす整数 S_M+1 として最小の値を求めよ．

Input

入力データセットは複数のケースから構成される．各ケースは次のような形式である．

N M
S₁ k₁ c_1,1 ... c_1,k1
...
S_M k_M c_M,1 ... c_M,kM

1 行目には，解答者の数 N と最後の問題を除いた問題の個数 M が与えられる． 続く M 行には，問題 1 〜 M についての解答できる可能性のある解答者の情報が与えられる．そのうち i 行目には，i 問目の得点 S_i と，i 問目に正解する可能性がある解答者の人数 k_i が与えられ，またその直後に k_i 個の数 c_i,1 ... c_i,ki が与えられる．c_i,j (1 ≤ j ≤ k_i) はそれぞれ ，i 問目に正解する可能性がある解答者の番号を表す．

入力の終わりは 2 つのゼロからなる行で示す．データセットの個数は最大でも 30 個を超えない．

入力で与えられる数値は全て整数であり，以下の条件を満たす．

• 2 ≤ N ≤ 10,000
• 1 ≤ M ≤ 1,000
• 1 ≤ S_i ≤ 100
• 1 ≤ k_i ≤ N
• 1 ≤ c_i,1 < ... < c_i,ki ≤ N
• Σk_i ≤ 100,000

ただし，出力すべき S_M+1 はこの範囲を超える場合があることに注意せよ．

Output

各データセットについて条件を満たすような最後の問題の点数 S_M+1 の最小値を 1 行に出力せよ．

Sample Input

3 2
5 2 1 3
8 2 2 3
2 3
8 2 1 2
3 1 1
5 1 2
2 5
100 1 1
100 1 1
100 1 1
100 1 1
100 1 1
3 4
5 1 1
5 1 2
100 2 1 3
100 2 2 3
0 0

Output for Sample Input

14
11
501
196

---