{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003eJAG 模擬予選練習会\u003c/h3\u003e\n\n\u003cp\u003eACM-ICPC OB/OGの会 (Japanese Alumni Group; JAG) には模擬コンテストで出題する問題のストックが \u003ci\u003eN\u003c/i\u003e 問あり,それぞれの問題は 1 から \u003ci\u003eN\u003c/i\u003e の整数で番号付けられている.\nそれぞれの問題について難易度評価と推薦投票が行われており,問題 \u003ci\u003ei\u003c/i\u003e の難易度は \u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e で,推薦度は \u003ci\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e である.\nまた,難易度の最大値は \u003ci\u003eM\u003c/i\u003e である.\n\u003c/p\u003e\n\n\u003cp\u003e次のコンテストでは,難易度 1 から \u003ci\u003eM\u003c/i\u003e の問題をそれぞれ 1 問ずつ,計 \u003ci\u003eM\u003c/i\u003e 問出題する予定である.\nコンテストのクオリティを上げるために推薦度の合計が最大になるように問題を選定したい.\nただし,JAG の作問力はすさまじいので,各難易度の問題が最低でも 1 問以上ずつあると仮定してよい.\n\u003c/p\u003e\n\n\u003cp\u003eあなたの仕事は,条件を満たすように問題を選定したときの推薦度の和の最大値を求めるプログラムを作成することである.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\n\u003cp\u003e入力は複数のデータセットからなる.\n各データセットは次の形式で表される.\n\u003c/p\u003e\u003cblockquote\u003e\u003ci\u003eN\u003c/i\u003e \u003ci\u003eM\u003c/i\u003e\u003cbr\u003e\u003ci\u003ed\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ev\u003csub\u003e1\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e...\u003cbr\u003e\u003ci\u003ed\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e \u003ci\u003ev\u003csub\u003eN\u003c/sub\u003e\u003c/i\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\u003cp\u003eデータセットの 1 行目には,問題ストックの数を表す整数 \u003ci\u003eN\u003c/i\u003e と,難易度の最大値 \u003ci\u003eM\u003c/i\u003e が空白区切りで与えられる.\nこれらの数は \u003ci\u003e1 ≤ M ≤ N ≤ 100\u003c/i\u003e を満たす.\n続く \u003ci\u003eN\u003c/i\u003e 行の内 \u003ci\u003ei\u003c/i\u003e 行目には,問題 \u003ci\u003ei\u003c/i\u003e の難易度と推薦度を表す整数 \u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e と \u003ci\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e が空白区切りで与えられる.\nこれらの数は \u003ci\u003e1 ≤ d\u003csub\u003ei\u003c/sub\u003e ≤ M\u003c/i\u003e および \u003ci\u003e0 ≤ v\u003csub\u003ei\u003c/sub\u003e ≤ 100\u003c/i\u003e を満たす.\nまた,各 \u003ci\u003e1 ≤ j ≤ M\u003c/i\u003e について,\u003ci\u003ed\u003csub\u003ei\u003c/sub\u003e \u003d j\u003c/i\u003e となる \u003ci\u003ei\u003c/i\u003e が 1 つ以上存在することが保証される.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\u003cp\u003e入力の終わりは空白で区切られた 2 つのゼロで表される.\nまた,データセットの数は 50 を超えない.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\n\u003cp\u003e各データセットについて,各難易度から 1 問ずつ出題するときの,出題する問題の推薦度の和の最大値を 1 行に出力せよ.\n\u003c/p\u003e\u003cblockquote\u003e\u003c/blockquote\u003e\n\n\u003ch3\u003eSample Input\u003c/h3\u003e\n\n\u003cpre\u003e5 3\n1 1\n2 3\n3 2\n3 5\n2 1\n4 2\n1 7\n2 1\n1 3\n1 5\n6 1\n1 3\n1 2\n1 8\n1 2\n1 7\n1 6\n20 9\n4 10\n2 4\n5 3\n6 6\n6 3\n7 4\n8 10\n4 6\n7 5\n1 8\n5 7\n1 5\n6 6\n9 9\n5 8\n6 7\n1 4\n6 4\n7 10\n3 5\n19 6\n4 1\n6 5\n5 10\n1 10\n3 10\n4 6\n2 3\n5 4\n2 10\n1 8\n3 4\n3 1\n5 4\n1 10\n1 3\n5 6\n5 2\n1 10\n2 3\n0 0\n\n\u003c/pre\u003e\n\u003cp\u003e\nサンプルのデータセットは5つあり,順に\u003cbr\u003e\n1行目から6行目までが1つ目 (\u003ci\u003eN\u003c/i\u003e \u003d 5, \u003ci\u003eM\u003c/i\u003e \u003d 3) のテストケース,\u003cbr\u003e\n7行目から11行目までが2つ目 (\u003ci\u003eN\u003c/i\u003e \u003d 4, \u003ci\u003eM\u003c/i\u003e \u003d 2) のテストケース,\u003cbr\u003e\n12行目から18行目までが3つ目 (\u003ci\u003eN\u003c/i\u003e \u003d 6, \u003ci\u003eM\u003c/i\u003e \u003d 1) のテストケース,\u003cbr\u003e\n19行目から39行目までが4つ目 (\u003ci\u003eN\u003c/i\u003e \u003d 20, \u003ci\u003eM\u003c/i\u003e \u003d 9) のテストケース,\u003cbr\u003e\n40行目から59行目までが5つ目 (\u003ci\u003eN\u003c/i\u003e \u003d 19, \u003ci\u003eM\u003c/i\u003e \u003d 6) のテストケースをそれぞれ表す.\n\u003c/p\u003e\n\n\u003ch3\u003eOutput for Sample Input\u003c/h3\u003e\n\n\u003cpre\u003e9\n8\n8\n71\n51\u003c/pre\u003e\n"}}]}