Water Facilities Construction

In a distant kingdom, one side is graced with a beautiful lake while the other is bordered by an endless desert. The kingdom is divided into an N×M rectangular grid, where each cell represents a city with a given altitude. The altitude of the city in row \(i\) and column \(j\) is denoted by \(h_{i,j}\).

To ensure that every resident can enjoy the clear lake water, two types of water facilities may be constructed in some cities:

• Water Plant: This facility pumps water from the lake to the city’s reservoir. Due to its proximity to the lake, a water plant can only be built in a city on the first row (i.e. row 1).
• Water Station: Using water pipelines and the advantage of elevation differences, a water station can transport lake water from a higher altitude city to a lower altitude adjacent city. In order for a city to build a water station, it must have at least one adjacent (sharing a common side) city with higher altitude that already has a water facility (either a water plant or a water station).

Since all cities in the last row (row \(N\)) are located near the desert (a dry region), each of these cities must have a water facility. Your task is to decide if this requirement can be met, and:

• If it is possible, compute the minimum number of water plants (in row 1) needed so that, via subsequent water stations, every city in row \(N\) can eventually have a water facility.
• If it is impossible, determine the number of cities in row \(N\) that cannot possibly be provided with a water facility.

Note that a water station in a city \(v\) can be built only if there exists an adjacent city \(u\) with a water facility such that:

[ h_{u} > h_{v} ]

You may assume that if a water plant is built in a city on the first row, then it automatically has a water facility. Similarly, any city provided with a water facility (by either method) can serve as the source for constructing water stations in its lower-altitude neighbors.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of rows and columns, respectively).

Then \(N\) lines follow. The \(i\)-th of these lines contains \(M\) integers \(h_{i,1}, h_{i,2}, \dots, h_{i,M}\) representing the altitudes of the cities in row \(i\).

outputFormat

If it is possible to provide all cities in row \(N\) with a water facility following the rules described, output a single integer representing the minimum number of water plants (to be built in row 1) required. Otherwise, output a single integer representing the number of cities in row \(N\) that cannot possibly have any water facility.

sample

3 3
10 9 8
7 6 5
4 3 2

1