“Sentiment is a chemical defect found on the losing side” -Sherlock

Problem 6

You are given a matrix of size n x m. Now you need to pick exactly one element from each row to make a new array of size n. These elements should be picked in such a way that sum of absolute difference between adjacent elements is minimum.

Input :

First line of the input consists of two positive integers n and m .

Each of the next n lines contains m space separated integers denoting the matrix $mat$.

Output:

A single integer representing minimum cumulative sum of adjacent elements.

Constraints:

$1 \le n,m \le 5 \cdot 10^2$

$1 \le$mat[i][j]$\le 10^{7}$