白金莲花池

题目背景

为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格(1≤M,N≤30)。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝还可能掩藏着宝藏的水。 贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。 贝西的舞步很像象棋中的马步:每次总是先横向移动一格,再纵向移动两格,或先纵向移动两格,再横向移动一格。最多时,贝西会有八个移动方向可供选择。 约翰一直在观看贝西的芭蕾练习,发现她有时候不能跳到终点,因为中间缺了一些荷叶。于是他想要添加几朵莲花来帮助贝西完成任务。

题目描述

但是!约翰在种植莲花的时候发现了一件很有趣的事,有些格子是不能直接种植莲花的,原因是……实不相瞒,无法直接种植莲花的格子的泥土中大部分都是货真价实的铂金,正是它们妨碍了莲花的正常生长!而恰好约翰刚刚学到了铂金的开采方法,也有相关的开采工具,而且他还发现开采铂金后的格子就可以正常地种植莲花,不必担心泥土缺失的问题。(由于贝西迫切地想练习,所以约翰不会开采不打算种莲花的铂金格子) 开采铂金很累,就像是种植莲花一样累,它们都会消耗掉约翰一点体力(也就是说想把铂金格子变成莲花格子需要两点体力),约翰最初有P点体力来种植莲花或开采铂金。 请帮助约翰计算至少需要消耗多少体力才能帮助贝西完成任务,这个数字记作S,以及有多少种消耗这些体力的方法能帮助贝西完成任务,这个数字记作WS;铂金当然是越多越好,请计算在消耗S点体力帮助贝西完成任务的同时最多能开采多少铂金,这个数字记作G,以及消耗S点体力开采G块铂金帮助贝西完成任务的方法数,这个数字记作WG。 若在P点体力内无法帮助到贝西,那么只输出-1。 若在S点体力内无法开采铂金,那么第二行只输出-1。

输入输出格式

输入格式


第一行:三个用空格分开的整数:P,M和N 第二行到M+1行:第i+1行有N个用空格分开的整数,描述了池塘第i行的状态: 0为水,1为莲花,2为岩石,3为贝西所在的起点,4为贝西想去的终点,5为铂金的埋藏地。

输出格式


第一行:S WS(两个整数,需要最少消耗的体力及方案数;如果无法帮助,输出-1。) 第二行:G WG(两个整数,在消耗最少的前提下开采最多的铂金数及方案数,若在S点体力内无法开采铂金,第二行输出-1。) 如果第一行是-1,不要输出第二行。 保证输出的数字不会超过一个64位的有符号整数。

输入输出样例

输入样例 #1

4 5 6
0 0 0 1 0 0
2 0 0 2 0 0
0 0 5 0 0 0
3 0 0 0 4 0
0 0 2 0 0 0

输出样例 #1

2 2
1 1

输入样例 #2

3 3 2
3 5
4 2
0 1

输出样例 #2

-1

说明

约翰可以用开采到的铂金小赚一笔,但如果用多余的体力开采铂金而不往上种莲花的话贝西会很生气!