{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"F.さんは大臣に文書に署名してもらいたいと考えています。大臣は、文書が彼の省によって承認されている場合にのみ署名をします。省はM階建てのビルで、階は1からMまで番号が付けられています(1\u0026lt;\u003dM\u0026lt;\u003d100)。各階にはN部屋(1\u0026lt;\u003dN\u0026lt;\u003d500)があり、部屋にも1からNまで番号が付けられています。各部屋には1人(ただし1人のみ)の公務員がいます。 \r\u003cbr\u003e\r\u003cbr\u003e文書は、M階の少なくとも1人の公務員によって署名されている場合にのみ省によって承認されます。公務員は、以下のいずれかの条件が満たされている場合にのみ文書に署名をします: \r\u003cbr\u003e\u003cblockquote\u003ea. 公務員が1階で働いている場合; \r\u003cbr\u003eb. 同じ番号の部屋にいる公務員によって文書が署名されている場合(ただし、その部屋は1階下に位置する); \r\u003cbr\u003ec. 隣接する部屋にいる公務員によって文書が署名されている場合(隣接する部屋とは、同じ階にあり、番号が1つ異なる部屋を指します)。 \u003c/blockquote\u003e\r\u003cbr\u003e各公務員は文書に署名するための手数料を徴収します。手数料は10^9を超えない正の整数です。 \r\u003cbr\u003e\r\u003cbr\u003e文書を承認するための最も安価な方法を見つける必要があります。 \r\u003cbr\u003e\r\u003cbr\u003e"}},{"title":"入力","value":{"format":"HTML","content":"入力ファイルの最初の行には、スペースで区切られた2つの整数が含まれています。最初の整数Mはビルの階数を表し、2番目の整数Nは各階の部屋数を表します。次のM行には、手数料を示すN個の整数がスペースで区切られて含まれています(l階のk番目の整数は、l階のk番目の部屋で働いている公務員が要求する手数料です)。"}},{"title":"出力","value":{"format":"HTML","content":"文書を最も安価な方法で承認するために訪れるべき部屋の番号を(1行に1つずつ)出力してください。最も安価なコストに至る方法が複数ある場合は、そのいずれかを出力しても構いません。"}},{"title":"サンプル","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\r\n10 10 1 10\r\n2 2 2 10\r\n1 10 10 10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3\r\n2\r\n1\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"ヒント","value":{"format":"HTML","content":"各公務員には、文書の承認を得る方法が常に存在する(1階からその公務員までを含めて)ことを仮定できます。手数料は10^9を超えないようにしてください。 \r\u003cbr\u003eこの問題は非常に大きな入力データを持っているため、時間制限を超えないようにscanf()を使用してデータを読み取ることをお勧めします。"}}]}