Background

Description

John’s cousin Ron lives in Colorado. He plans to teach his cows to ski, but they are very shy and do not dare to ski at tourist resorts. So he has to build his own ski area. Ron’s ski area can be divided into $W$ columns and $L$ rows ($1 \le W \le 500$, $1 \le L \le 500$). Each cell has a specific height $H$ ($0 \le H \le 9999$). Cows can ski between adjacent cells, and they are not allowed to move from a lower cell to a higher one.

To ensure that any two cells can reach each other, Ron plans to build some direct lifts. Lifts are powerful: they can connect any two cells and are bidirectional. Multiple lifts can be built at the same cell. However, lifts are very expensive, so he wants to build as few as possible. What is the minimum number of lifts needed?

Output Format

Output the minimum number of lifts needed.

9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1

3

Hint

Constraints: $1 \le W, L \le 500$, $0 \le H \le 9999$.

Translated by ChatGPT 5