Problem Background

You proudly fly far away, while I rest on the leaves.
The inaudible declaration, repeated many years.
The longing of the sea and the moon has transformed my yesterday,
In my mature smile,
You never glanced once.

Problem Description

Cicada Charlie is going to find his good friend, the bird.

Specifically, the place where Charlie and his friend live can be seen 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)$, pass through each cell in the grid exactly once without repetition, and finally return to his home $(x_0,y_0)$. Charlie has two ways of moving:

1. Jump. With this method, Charlie can reach one of the four adjacent cells (up, down, left, right) that has a strictly lower altitude than the current cell. Note that jumping does not consume energy.
2. Fly. With this method, Charlie can fly from the current cell $(x,y)$ to any cell $(x',y')$ in the grid, consuming $h_{x',y'}-h_{x,y}$ units of energy. Note that the energy consumed by flying can be negative.

Charlie wants to complete his goal with the least number of flights, and under this premise, to minimize the energy consumed. Given the large size of the grid, Charlie hopes you can help him.

Input Format

The first line contains four integers, representing $n, m, x_0, y_0$, as described above.
The next $n$ lines, each containing $m$ integers, represent the altitude $h_{i,j}$ of cell $(i,j)$.

Output Format

One line containing two integers, representing the "minimum number of flights" and the "minimum energy consumed under the condition of the least number of flights".

Sample Input and Output

Input Sample #1

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

Output Sample #1

1 8

Input Sample #2

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

Output Sample #2

5 4

Input Sample #3

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

Output Sample #3

7 25

Input Sample #4

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

Output Sample #4

36 254

Notes/Hints

This problem uses bundled testing

Sample 1 Explanation: Fly from $(1,1)$ to $(2,2)$, then go around in a circle.

Sample 2 Explanation: One optimal solution is: $(2,3)-(1,3)-(1,2)-(1,1)=(2,1)-(3,1)=(2,2)=(3,2)=(3,3)=(2,3)$, where $=$ represents flying.

• Subtask 1 (10 pts): Satisfies $1 \leq n,m \leq 3$.
• Subtask 2 (20 pts): Satisfies $1 \leq n,m \leq 5$.
• Subtask 3 (20 pts): Guarantees at most two different altitudes.
• Subtask 4 (50 pts): No special restrictions.

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 Author: 冷月葬T魂

见题面 Input 部分

见题面 Output 部分