Charlie’s Journey: Minimizing Flight Moves and Energy Consumption

Charlie wants to find his friend Feina. He lives in a region modeled as an \(n \times m\) grid. The grid cells are indexed from \((1,1)\) at the top‐left corner to \((n,m)\) at the bottom‐right corner. Each cell \((i,j)\) has an integer elevation \(h_{i,j}\).

Charlie starts at his home cell \((x_0,y_0)\) and wishes to perform a Hamiltonian cycle on the grid: visit every cell exactly once and return to his starting cell. He has two types of moves:

1. Jump: He can move to one of the four adjacent cells (up, down, left, right) provided that the elevation of the target cell is strictly lower than his current cell. This move costs no energy and does not count as a flight.
2. Flight: He can fly to any cell in the grid. This move consumes \(h_{dest} - h_{src}\) units of energy (which can be negative) and counts as one flight.

His primary objective is to minimize the number of flights used. Under that constraint, he wants to minimize the total energy consumption.

Your task is to compute the lexicographically minimal pair \((F, E)\), where \(F\) is the minimum number of flights required and \(E\) is the corresponding minimum total energy consumption, for Charlie to complete his journey.

Note: A jump move is only available if the target cell is adjacent (up, down, left or right) and its elevation is strictly less than the current cell. Otherwise, Charlie has to use a flight move.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 4)\) representing the dimensions of the grid. (Note: Since the problem is NP-hard in general, we keep the grid small.)

The next \(n\) lines each contain \(m\) integers, representing the elevation values \(h_{i,j}\) for the grid cells.

The last line contains two integers \(x_0\) and \(y_0\) \((1 \le x_0 \le n, 1 \le y_0 \le m)\) denoting Charlie's home cell.

outputFormat

Output two space‐separated integers: the minimum number of flights \(F\) and the corresponding minimal total energy consumption \(E\) for Charlie to complete his journey.

sample

1 1
5
1 1

0 0