{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"在韩国,小青蛙cheonggaeguri的淘气是传奇的。这是当之无愧的名声,因为这些青蛙会在夜间跳跃穿过你的稻田,压扁稻谷。早晨,在记录下哪些植物被压扁后,你想要确定造成最大破坏的青蛙的路径。青蛙总是沿着直线跳跃穿过稻田,每一次跳跃的长度都相同:\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/2b569feff82fa0c264f6d8ac5bf43ad5?v\u003d1719236253\"\u003e \u003cbr\u003e你的稻田上的植物排列在一个网格的交点上,如图1所示,讨厌的青蛙从你的稻田外部开始完全跳跃穿过你的稻田,最终在另一侧的稻田外部结束,如图2所示:\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/dfe973006322e3d7d69b5b94b6984d51?v\u003d1719236253\"\u003e \u003cbr\u003e许多青蛙可以跳过稻田,从一个稻谷到另一个稻谷跳跃。每次跳跃都会落在一个植物上并将其压扁,如图3所示。请注意,一些植物可能在夜间被多只青蛙着陆。当然,你看不到显示青蛙路径或任何跳跃的线条超出你的稻田范围,对于图3中的情况,你所能看到的显示在图4中:\u003cbr\u003e\u003cimg src\u003d\"CDN_BASE_URL/5ca1beb49abcad87752bf417b264256b?v\u003d1719236253\"\u003e \u003cbr\u003e根据图4,你可以重建青蛙可能穿过你的稻田的所有可能路径。你只对在其穿越稻田的过程中着陆在至少3株稻谷上的青蛙感兴趣。这样的路径被称为青蛙路径。在这种情况下,这意味着图3中显示的三条路径是青蛙路径(还有其他可能的青蛙路径)。沿着第1列向下的垂直路径可能是一条跳跃长度为4的青蛙路径,但由于只有2株植物被压扁,所以我们不感兴趣;包括第2行第3列、第3行第4列和第6行第7列的对角线路径有三株扁平植物,但没有固定的跳跃长度可以使跳跃以这种方式间隔而仍然落在至少3株植物上,因此它不是一条青蛙路径。还要注意,沿着青蛙路径的线路可能会有额外的被压扁的植物,这些植物不需要被该路径着陆(请参见图4中横穿第2行的水平路径上的(2,6)位置的植物),实际上一些被压扁的植物可能根本无法解释为任何青蛙路径。 \u003cbr\u003e \u003cbr\u003e你的任务是编写一个程序来确定任何单条青蛙路径中着陆的最大数量(最大值是针对所有可能的青蛙路径)。在图4中,答案是7,来自第6行的青蛙路径。"}},{"title":"输入","value":{"format":"HTML","content":"您的程序需要从标准输入中读取。第一行包含两个整数R和C,分别表示你的稻田中的行数和列数,1 \u003c\u003d R,C \u003c\u003d 5000。第二行包含一个整数N,表示被压扁的稻谷植物的数量,3 \u003c\u003d N \u003c\u003d 5000。接下来的N行中,每行包含两个整数,分别为一个被压扁的稻谷植物的行号(1 \u003c\u003d 行号 \u003c\u003d R)和列号(1 \u003c\u003d 列号 \u003c\u003d C),用一个空格分隔。每个被压扁的植物只列出一次。"}},{"title":"输出","value":{"format":"HTML","content":"您的程序需要写入标准输出。输出包含一行,一个整数,表示如果存在至少一条青蛙路径,则造成最大破坏的青蛙路径上被压扁的植物数量,否则为0。"}},{"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\u003e6 7\r\n14\r\n2 1\r\n6 6\r\n4 2\r\n2 5\r\n2 6\r\n2 7\r\n3 4\r\n6 1\r\n6 2\r\n2 3\r\n6 3\r\n6 4\r\n6 5\r\n6 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}