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.
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.
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).
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 |