Minimum Replacements to Achieve Strictly Increasing Matrix

You are given an n × m matrix of integers. Your task is to replace the minimum number of entries such that every row becomes strictly increasing from left to right and every column becomes strictly increasing from top to bottom.

For any cell at position \( (i,j) \) (with 0-based indices), if the current value is not greater than the value immediately above it (if it exists) or to the left of it (if it exists), you must replace that cell with the value \( \max\{ matrix[i-1][j],\; matrix[i][j-1] \} + 1 \). The goal is to minimize the number of such replacements.

Note: The operation is applied in a single left-to-right, top-to-bottom pass, and once a cell is replaced, the updated value is used for subsequent comparisons.

inputFormat

The input is read from stdin and has the following format:

n m
row1_element1 row1_element2 ... row1_elementm
row2_element1 row2_element2 ... row2_elementm
... 
rown_element1 rown_element2 ... rown_elementm

Where n and m are positive integers representing the number of rows and columns, respectively.

outputFormat

Output a single integer to stdout — the minimum number of replacements made to achieve a strictly increasing matrix by rows and columns.

3 3
1 2 3
4 2 6
7 8 9

1