题目描述

期末考试结束后，ccvg老师要给他们班级的同学们进行奖励，给他们分发糖果，但是由于ccvg老师最近购入了最新的5090显卡，导致目前钱包空空，所以ccvg老师在希望尽可能少的发放糖果，但是发放糖果需要满足以下两个原则：

1. 公平性要求：每位同学至少分到 1 颗糖果。
2. 比较满意：对于相邻的同学（即四周上下左右相邻座位的同学），分数较高的同学必须比分数较低的同学获得更多的糖果。

班级的座位排布为 m x n ,网格中的每个格子表示一个同学的座位。给定一个二维数组 scores，其中 scores[i][j] 表示第 i 行第 j 列同学的分数。

奇怪的是，ccvg老师发现，大家这次考试的分数没有相同的。

老师需要按照上述规则分配糖果，求满足条件的 最少糖果总数。

输入格式

1. 第一行输入两个正整数 m 和n，表示班级的行数和列数。
2. 接下来的 m 行，每行包含n个非负整数，表示二维数组 scores ，scores[i][j] 表示坐在第 i 行，第 j 列的同学的分数，scores中不会出现重复。

输出格式

输出一个整数，表示满足条件的最少糖果总数。

样例输入

3 3
1 7 2
3 4 9
5 10 12

样例输出

27

样例解释

分数如下：

1 0 2
3 4 9
5 10 12

糖果分配如下：

1 4 1
2 3 4
3 4 5

数据范围

2 < m, n < 1000

scores[i][j] < 1e9