小核桃的月赛奖品

题目描述

健胃消食片被偷走了，偷走的人藏到了一个 $k \times k$ 的方格迷宫中，小核桃想找到健胃消食片，他有$x$点体力，每走一格会消耗$1$点体力值，同时消耗$y$点时间，不可以碰到迷宫的墙，小核桃太懒了，所以想用最少的体力走到最后，他的量子眼睛可以探查到$3 \times 3$范围内的方格，小核桃也可以选择休息，休息一次可以回复$1$点体力值，但同时会消耗$y$点时间，他的妈妈 (别管小核桃他妈妈是谁qwq) 让他在$n$点之前必须回家(n点回家也可以)，现在请你制作一个程序，帮他计算路径吧！

输入输出描述：

输入

第一行：$x ,y, n$三个正整数 第二行：一个整数 $k$ 接下来 $k$ 行，每行 $k$ 个整数，表示迷宫状态 （0为空，1为障碍，2为起点，3为健胃消食片位置）

输出

小核桃的用时和最终剩余体力值

要求：

体力使用要最少，同时用时最少（尽量保持两个都最小）

体力不能小于0（可以等于0），同时用时可以等于n，但不能超过n

样例：

10 2 20
3
0 0 0
0 1 0
2 0 3

4 8

示意图

数据规模与约定

对于100%的数据，保证 $1 \leq x, y, n \leq 1000, 1 \leq k \leq 10$,同时保证有解