众所周知,在草帽海贼团路飞一行人隐世修行2年后,准备进入新世界冒险时,误闯入圣地马力乔亚海底10,000米的鱼人岛,并发现了鱼人霍德的阴谋,为拯救鱼人岛的民众,粉粹他的阴谋,路飞9人在琼科尔德广场与霍德率领的新鱼人海贼团与飞行海贼团10万人进行决战。最终粉碎了他们的阴谋,并救下了鱼人岛的国王和人鱼公主。为报答路飞一行人,鱼人公主带路飞进入了一个神奇并充满宝藏的屋子。
屋子大小D*D,我们可以把地面分成D行*D列个方格,每个位置用坐标表示[i , j ](1<=i,j<=D),每个位置有不同价值的宝藏。而四面墙壁上有着虫洞一样的东西,(上北,下南,左西,右东)即如果你从西面的墙壁上虫洞进去,就会从东面的墙壁穿出来,如果你从南面的墙壁上虫洞进去,就会从北面的墙壁穿出来。假设D=3,坐标A[2,3]表示在第二行的第3列的地点. 如果你从A点继续向东走,就会通过类似虫洞的东西一样,就会到达【2,1】。如果你从【3,2】继续向南走,就会从【1,2】出来,
刚进去宝藏屋的人可以以任意位置作为探索的起点,而且到达落点后只能往东或者往南走。因为时间问题,你只会以起点开始探索N行M列的范围(比如起点是1, 1,N是2,M是3的话你的探索位置就有(1,1),(1,2),(1,3),(2,1),(2,2)(2,3)这6个点
因为有贪财猫娜美,所以他们都能清楚知道每个位置宝藏的价值,并标上价值,他们想要拿到最多的宝藏(假设可以拿无限的宝藏,并且经过每个位置直接把宝藏全部拿走),路飞向聪明的你求助,请你求出落地点和最大收获。
输入有多组,每组数据第一行输入三个正整数D N M(0<N,M<=50,0<D<=50)
第2行至第d+1行每一行有d个数列出了此行每一列对应位置的宝藏价值pi(0<=pi<1000)
对于每一个测试数据 ,每行3个数,求出最大收获的落地点(取行最小的,如果行相同,取列最小的)和最大收获,当输入0 0 0时结束。
样例中当落点为【2,3】时探索位置有(【2,3】,【3,3】,【2,1】,【3,1】)和为12,