P8254弱肉强食 | ||
|
问题描述
一片海洋相当于一张$n \times m$的网格,其中每个格子里面都有一条鱼。其中,$(s,t)$这个格子的鱼是一条鲨鱼。
海洋是一个弱肉强食的社会,鲨鱼可以吃掉别的体型小于它的鱼。具体来说,假设当前鲨鱼的体型为$x$,而另一条鱼的体型为$y$;如果$x>y$,那么鲨鱼就可以消灭它,并让自己的体型变为$x+y$。
鲨鱼可以自由地在网格中上下左右移动,且移动步数不受限制。当鲨鱼试图移动到一个已经有其它鱼的格子里时,鲨鱼就会尝试吃掉它;如果鲨鱼无法吃掉它,那么鲨鱼就无法进入它所占据的那一格。
现在,请问鲨鱼最多吃掉的鱼的数量,以及鲨鱼最终体型的最大值?
输入格式
第一行,输入两个整数$1 \leqslant n, m \leqslant 10^3$,表示网格的大小;
第二行,输入两个整数$1 \leqslant s \leqslant n, 1 \leqslant t \leqslant m$,表示鲨鱼的初始位置;
接下来$n$行,每行输入$m$个正整数,其中第$i$行第$j$个整数表示该位置鱼的体型(若该位置为鲨鱼,则表示鲨鱼的初始体型);所有鱼的体型均不超过$10^9$。
输出格式
输出一行两个整数,分别表示鲨鱼最多吃掉的鱼的数量,以及鲨鱼最大的体型。
样例输入
3 3
2 2
8 1 2
7 2 5
6 5 1
样例输出
2 5