{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003eクイズ\u003c/h3\u003e\n\n\u003cp\u003eあなたはクイズ番組のディレクターである.\nクイズ番組には解答者として \u003ci\u003eN\u003c/i\u003e 人が出演予定であり,それぞれ 1 から \u003ci\u003eN\u003c/i\u003e まで番号付けられている.\n\u003c/p\u003e\n\n\u003cp\u003e問題は \u003ci\u003eM+1\u003c/i\u003e 問出題する予定であり,それぞれの問題は 1 から \u003ci\u003eM+1\u003c/i\u003e まで番号付けられている.\n問題は番号順に出題され,それぞれ早押しで最初に正解した人にのみ得点が入る.\u003ci\u003ei\u003c/i\u003e 問目の問題の得点は整数 \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e である.\n\u003ci\u003eM+1\u003c/i\u003e 問目の問題を終えた時点で総合得点が最大の人が優勝する.\nただし,最大得点の人が複数人存在する場合,優勝者は存在しない.\n\u003c/p\u003e\n\n\u003cp\u003e現在 \u003ci\u003eM\u003c/i\u003e 問目まで配点を決めたので,\u003ci\u003eM+1\u003c/i\u003e 問目の配点を決めようと考えている. \n最後の問題は,誰でも逆転できる点数にするのがクイズ番組のお約束である. \nしかし,その場で解答者たちの総合得点を見て問題の点数を決めると,解答者たちのやる気を削ぐ可能性がある.そこで, どんな点数状況でも全員に逆転のチャンスがあるような点数設定をあらかじめ考えることにした.\n\u003c/p\u003e\n\n\u003cp\u003e幸い,1 から \u003ci\u003eM\u003c/i\u003e 問目まではそれぞれ正解する可能性がある解答者が分かっている.\u003ci\u003eM+1\u003c/i\u003e 問目は全員が正解する可能性のある問題である.正解する可能性がある解答者の中で,早押しで正解した1名のみが問題の得点 \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e を得る.問題への解答は正解した解答者が現れた時点で締め切られ,同じ解答者は何度でも解答を行うことができるため,ある問題の得点 \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e を誰も得られない場合は考慮しなくてよい.また,複数人の解答者がある問題の得点 \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e を重複して獲得したり,得点を分け合ったりすることもない. \n\u003c/p\u003e\n\n\u003cp\u003e各問の配点と正解可能な解答者の情報を基に, 起こりうるどのような得点状況においても,最後の問題を正解すれば必ず誰でも優勝できるように最後の問題の点数 \u003ci\u003eS\u003csub\u003eM+1\u003c/sub\u003e\u003c/i\u003e を設定したい. 条件を満たす整数 \u003ci\u003eS\u003csub\u003eM+1\u003c/sub\u003e\u003c/i\u003e として最小の値を求めよ.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力データセットは複数のケースから構成される.各ケースは次のような形式である.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003eN\u003c/i\u003e \u003ci\u003eM\u003c/i\u003e\u003cbr\u003e\u003ci\u003eS\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ek\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ec\u003csub\u003e1,1\u003c/sub\u003e\u003c/i\u003e ... \u003ci\u003ec\u003csub\u003e1,k\u003csub\u003e1\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e...\u003cbr\u003e\u003ci\u003eS\u003csub\u003eM\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ek\u003csub\u003eM\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ec\u003csub\u003eM,1\u003c/sub\u003e\u003c/i\u003e ... \u003ci\u003ec\u003csub\u003eM,k\u003csub\u003eM\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e\u003c/blockquote\u003e\n\n\n\u003cp\u003e1 行目には,解答者の数 \u003ci\u003eN\u003c/i\u003e と最後の問題を除いた問題の個数 \u003ci\u003eM\u003c/i\u003e が与えられる.\n続く \u003ci\u003eM\u003c/i\u003e 行には,問題 1 〜 \u003ci\u003eM\u003c/i\u003e についての解答できる可能性のある解答者の情報が与えられる.そのうち \u003ci\u003ei\u003c/i\u003e 行目には,\u003ci\u003ei\u003c/i\u003e 問目の得点 \u003ci\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e と,\u003ci\u003ei\u003c/i\u003e 問目に正解する可能性がある解答者の人数 \u003ci\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e が与えられ,またその直後に \u003ci\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e 個の数 \u003ci\u003ec\u003csub\u003ei,1\u003c/sub\u003e ... c\u003csub\u003ei,k\u003csub\u003ei\u003c/sub\u003e\u003c/sub\u003e\u003c/i\u003e が与えられる.\u003ci\u003ec\u003csub\u003ei,j\u003c/sub\u003e\u003c/i\u003e (\u003ci\u003e1 ≤ j ≤ k\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e) はそれぞれ ,\u003ci\u003ei\u003c/i\u003e 問目に正解する可能性がある解答者の番号を表す.\n\u003c/p\u003e\n\n\u003cp\u003e入力の終わりは 2 つのゼロからなる行で示す.データセットの個数は最大でも 30 個を超えない.\n\u003c/p\u003e\n\u003cp\u003e入力で与えられる数値は全て整数であり,以下の条件を満たす.\n\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u003ci\u003e2 ≤ N ≤ 10,000\u003c/i\u003e\n\u003c/li\u003e\u003cli\u003e \u003ci\u003e1 ≤ M ≤ 1,000\u003c/i\u003e\n\u003c/li\u003e\u003cli\u003e \u003ci\u003e1 ≤ S\u003csub\u003ei\u003c/sub\u003e ≤ 100\u003c/i\u003e\n\u003c/li\u003e\u003cli\u003e \u003ci\u003e1 ≤ k\u003csub\u003ei\u003c/sub\u003e ≤ N\u003c/i\u003e\n\u003c/li\u003e\u003cli\u003e \u003ci\u003e1 ≤ c\u003csub\u003ei,1\u003c/sub\u003e \u0026lt; ... \u0026lt; c\u003csub\u003ei,k\u003csub\u003ei\u003c/sub\u003e\u003c/sub\u003e ≤ N\u003c/i\u003e\n\u003c/li\u003e\u003cli\u003e \u003ci\u003eΣk\u003csub\u003ei\u003c/sub\u003e ≤ 100,000\u003c/i\u003e\n\u003c/li\u003e\u003c/ul\u003e\n\n\u003cp\u003eただし,出力すべき \u003ci\u003eS\u003csub\u003eM+1\u003c/sub\u003e\u003c/i\u003e はこの範囲を超える場合があることに注意せよ.\n\u003c/p\u003e\n\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\n\u003cp\u003e各データセットについて条件を満たすような最後の問題の点数 \u003ci\u003eS\u003csub\u003eM+1\u003c/sub\u003e\u003c/i\u003e の最小値を 1 行に出力せよ.\n\u003c/p\u003e\n\n\n\u003ch3\u003eSample Input\u003c/h3\u003e\n\n\u003cpre\u003e3 2\n5 2 1 3\n8 2 2 3\n2 3\n8 2 1 2\n3 1 1\n5 1 2\n2 5\n100 1 1\n100 1 1\n100 1 1\n100 1 1\n100 1 1\n3 4\n5 1 1\n5 1 2\n100 2 1 3\n100 2 2 3\n0 0\u003c/pre\u003e\n\n\u003ch3\u003eOutput for Sample Input\u003c/h3\u003e\n\n\u003cpre\u003e14\n11\n501\n196\u003c/pre\u003e\n"}}]}