Hide

Problem D
Height Preservation

Virtual Reality (VR) is one of the new trends for applications recently. Wearing a VR headset, you will be in an immersive virtual environment for education, collaboration, entertainment, etc.

\includegraphics[width=0.4\textwidth ]{vr.png}

To enhance user experience, ICPC establishes a VR room for users to walk and explore a virtual environment. The user can see virtual scenes through a VR headset and can feel the slope of the virtual terrain while walking in this VR room.

The floor of this VR room consists of $m \times n$ cells in $m$ rows and $n$ columns. The real height of each cell can be adjusted so that we can simulate a virtual terrain.

The cell at the intersection of the $i$-th row and the $j$-th column has the real height level $S_{i,j}$ and corresponds to the virtual height $H_{i,j}$ in the virtual scene. The key idea of virtual terrain simulation is to preserve only the relative order of cell heights in each row and each column:

  • In each row $i$ ($1 \leq i \leq m$), $S_{i,j}=S_{i,k}$ if $H_{i,j} = H_{i,k}$, and $S_{i,j} > S_{i,k}$ if $H_{i,j} > H_{i,k}$.

  • In each column $j$ ($1 \leq j \leq n$), $S_{i,j} = S_{k,j}$ if $H_{i,j} = H_{k,j}$, and $S_{i,j} > S_{k,j}$ if $H_{i,j} > H_{k,j}$.

Given the virtual height of all cells, your task is to determine the minimum number of different real height levels.

Input

  • The first line contains two positive integer numbers: $m$ and $n$, the number of rows and columns in the floor of the VR room respectively ($m \times n \leq 10^6$).

  • The $i$-th line of the following $m$ rows contains $n$ positive integer numbers $H_{i,j}$ ($H_{i,j} \leq 10^9$, the virtual height of cells in the $i$-th row).

Output

Display an integer number that is the minimum number of real height levels of cells in the floor of the VR room.

Sample Input 1 Sample Output 1
2 3
8 12 17
17 20 7
3

Please log in to submit a solution to this problem

Log in