Background

You proudly fly far away, while I rest on a leaf.
Unheard declarations have been repeated for many years.
The longing under the moon over the vast sea turned my yesterday into feathers,
On my mature smiling face,
You have never taken a single glance.

Problem Description

The cicada Charlie is going to look for his good friend, the bird.

More specifically, the place where Charlie and his friend live can be viewed as an $n \times m$ grid, with the top-left corner at $(1,1)$ and the bottom-right corner at $(n,m)$. Each cell $(i,j)$ has an altitude $h_{i,j}$. Charlie’s goal is to start from his home $(x_0,y_0)$, visit every cell in the grid exactly once with no repeats and no omissions, and finally return to his home $(x_0,y_0)$. Charlie has two ways to move:

1. Jump. With this method, Charlie can move to one of the $4$ adjacent cells (up, down, left, right) whose altitude is strictly lower than the current cell. Note that jumping does not consume stamina.
2. Fly. With this method, Charlie can move from the current cell $(x,y)$ to any cell $(x',y')$ in the grid, and it consumes $h_{x',y'} - h_{x,y}$ units of stamina. Note that the stamina cost of flying can be negative.

Charlie wants to finish the goal using as few flights as possible, and under that condition, make the total stamina cost as small as possible. Since the grid is very large, Charlie hopes you can help him.

Input Format

The first line contains four integers $n, m, x_0, y_0$, with the meanings described above.
The next $n$ lines each contain $m$ integers. The $j$-th number on the $i$-th line represents the altitude $h_{i,j}$ of cell $(i,j)$.

Output Format

Output one line with two integers: the minimum number of flights, and the minimum total stamina cost under the condition that the number of flights is minimized.

3 3 1 1
1 2 3
8 9 4
7 6 5

1 8

3 3 2 3
1 2 3
2 2 4
1 2 2

5 4

4 4 2 3
5 9 6 2
4 2 3 6
7 2 5 2
4 2 3 9

7 25

10 10 3 3
9 13 7 7 3 8 6 5 12 8
1 4 10 11 9 10 13 6 2 18
3 3 19 6 14 2 19 10 2 16
3 1 11 14 14 18 8 8 16 14
13 5 7 4 11 17 3 16 10 20
10 16 12 19 14 12 11 20 15 10
10 15 5 1 16 2 7 5 14 5
3 19 12 19 8 13 17 7 10 13
2 10 17 6 8 11 8 7 1 4
3 7 8 1 3 5 4 11 9 17

36 254

Hint

This problem uses bundled testdata.

Explanation for Sample 1: Fly from $(1,1)$ to $(2,2)$, then go around once.

Explanation for Sample 2: One optimal plan is $(2,3)-(1,3)-(1,2)-(1,1)=(2,1)-(3,1)=(2,2)=(3,2)=(3,3)=(2,3)$, where $=$ denotes flying.

• Subtask 1 (10 pts): $1 \leq n, m \leq 3$.
• Subtask 2 (20 pts): $1 \leq n, m \leq 5$.
• Subtask 3 (20 pts): There are at most two distinct altitude values.
• Subtask 4 (50 pts): No special constraints.

Constraints for $100\%$ of the data:

• $1 \leq n, m \leq 50$.
• $1 \leq x_0 \leq n, 1 \leq y_0 \leq m, 1 \leq h_{i,j} \leq 10^9$.

Problem setter: 冷月葬T魂

Translated by ChatGPT 5