{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"F先生想让一份文件被一位部长签署。部长只会签署经过他部门批准的文件。该部门是一座M层楼的建筑,楼层编号从1到M,1≤M≤100。每层有N个房间(1≤N≤500),也编号从1到N。每个房间里只有一位官员。\r\u003cbr\u003e\r\u003cbr\u003e只有当文件被M层的至少一位官员签署时,该文件才会被部门批准。官员只会签署文件,如果满足以下至少一种条件:\r\u003cbr\u003e\u003cblockquote\u003ea. 该官员在1楼工作;\r\u003cbr\u003eb. 文件由位于下面一层但房间号相同的官员签署;\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":"Input","value":{"format":"HTML","content":"输入文件的第一行包含两个整数,用空格分隔。第一个整数M代表建筑物楼层数,第二个整数N代表每层的房间数。接下来的M行每行包含N个用空格分隔的整数,描述费用(第l行的第k个整数是第l层第k个房间的官员所需的费用)。"}},{"title":"Output","value":{"format":"HTML","content":"你应该按照最便宜的方式打印房间号(每行一个),以便批准文件。如果有多种方式导致最便宜的费用,你可以打印其中任意一种。"}},{"title":"Sample","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":"Hint","value":{"format":"HTML","content":"你可以假设对于每位官员,总是存在一种方式可以在不超过10^9的费用下获得文件批准(从1楼到该官员的过程中)。\r\u003cbr\u003e这个问题有大量的输入数据,使用scanf()而不是cin来读取数据以避免超时。"}}]}