A community garden is laid out as a grid of m rows by n columns of planter cells, with row 0 at the top and row m-1 at the bottom; cell (r, c) currently holds a soil mound of height grid[r][c]. For structural reasons, every column must end up with soil heights that strictly increase as you move down from the top cell to the bottom cell: grid[r][c] must be less than grid[r+1][c] for every row r from 0 to m-2, in every column c. The only action available is adding one unit of soil to a single cell, which increases that cell's height by exactly 1 and counts as one operation; soil can never be removed. Determine the minimum total number of soil-adding operations needed so that every column's heights strictly increase from top to bottom.

Input format

• Line 1: two space-separated integers m and n, the number of rows and columns.
• Lines 2 through m+1: each line contains n space-separated integers, the heights of that row's cells from column 0 to column n-1.

Output format

Print a single integer: the minimum total number of soil-adding operations required.

Constraints

• 1 <= m, n <= 1000
• 1 <= m * n <= 2*10^5
• 0 <= grid[r][c] <= 10^5

2 2
1 5
1 5

2

3 2
3 1
3 1
3 1

6