Description

However! When planting lotus, John discovered something interesting: some cells cannot have lotus planted directly. The reason is… to be honest, the soil in those cells contains a lot of genuine platinum, which hinders lotus growth! Coincidentally, John has just learned how to mine platinum and has the tools for it, and he also found that after mining the platinum, the cell can be planted with lotus normally, without worrying about missing soil. (Because Bessie is eager to practice, John will not mine a platinum cell unless he also intends to plant a lotus there.)

Mining platinum is tiring, just like planting lotus. Each action consumes $1$ point of stamina (that is, turning a platinum cell into a lotus cell requires $2$ points of stamina). John initially has $P$ points of stamina to plant lotus or mine platinum.

Please help John compute the least stamina needed to help Bessie complete the task, denoted by $S$, and the number of ways to spend exactly that stamina to help Bessie, denoted by $W_S$. Since more platinum is better, also compute, among all solutions that spend $S$ stamina and help Bessie, the maximum amount of platinum that can be mined, denoted by $G$, and the number of ways to help Bessie while spending $S$ stamina and mining exactly $G$ pieces of platinum, denoted by $W_G$.

If it is impossible to help Bessie within $P$ points of stamina, output only -1.

If it is impossible to mine any platinum within $S$ points of stamina, then output only -1 on the second line.

Input Format

The first line: three integers separated by spaces: $P$, $M$, and $N$.

Lines $2$ to $M+1$: the $(i+1)$-th line contains $N$ integers separated by spaces, describing the state of row $i$ of the pond:

$0$ means water, $1$ means lotus, $2$ means rock, $3$ means Bessie’s starting cell, $4$ means Bessie’s destination, and $5$ means a platinum deposit.

Output Format

The first line: two integers separated by a space, $S$ and $W_S$ (the minimum stamina required and the number of methods to achieve it; if it is impossible to help Bessie within $P$ stamina, output -1).

The second line: two integers separated by a space, $G$ and $W_G$ (the maximum amount of platinum mined under the minimum-stamina condition and the number of methods to achieve it; if no platinum can be mined within $S$ stamina, output -1 on the second line).

If the first line is -1, do not output the second line.

All output numbers are guaranteed not to exceed long long.

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

2 2
1 1

3 3 2
3 5
4 2
0 1

-1

Hint

John might make a small profit by mining the platinum, but if he uses extra stamina to mine platinum without planting lotus on those cells, Bessie will be very angry!

Translated by ChatGPT 5