Lucky Chances
Lucky Chances is a lottery game. Each lottery ticket has a play field and a scratch area. The play field is a rectangular r × c field filled with numbers. The scratch area hides row and column numbers that specify the bet cell.
There are four possible winning directions: up, down, left and right. You win a direction if all numbers in this direction from the bet cell are strictly less than a number in the bet cell. And if the bet cell is on the edge of the grid, you win the corresponding direction automatically!
Larry wants to choose the ticket that has maximum total number of winning directions for all possible bet cells. Write a program that determines this number for the given grid.
Input
The first line contains two integers r and c (1 ≤ r, c ≤ 100) - the number of rows and columns in the grid.
The following r lines contain c integers each - the numbers printed on the grid. Each number is positive and does not exceed 1000.
Output
Output a single integer w - the total number of winning directions for the given grid.