logo AlgoBeat OnlineJudge
登录 注册

#215560. [CCPC 2025 哈尔滨站] 扫雪

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

大雪过后,小 w 需要打扫一下自己的院子,使得凹凸不平的雪堆看起来至少更整齐一些。小 w 的院子可以视作一个 的网格,第 行第 列的格子内覆盖了相对高度为 的积雪。小 w 有以下几种清理雪堆的操作:

  • 选择 ,将第 行第 列的雪堆推到下一行上,此操作会使得 此操作不需要代价。
  • 选择 ,将第 行第 列的雪堆推到下一列上。此操作会使得 此操作不需要代价。
  • 选择 ,给第 行第 列的雪堆造雪。此操作会使得 。此操作需要 的代价。
  • 选择 ,给第 行第 列的雪堆抽雪。此操作会使得 。此操作需要 的代价。

小 w 想要进行若干次操作使得所有 都为 ,且需要的代价最小。你能帮他计算一下最小的代价吗?

输入格式

输入第一行包含一个整数 (),表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据:

输入第一行包含两个整数 (),表示院子的行数与列数。

接下来 行第 行包含 个整数 (),第 个整数表示第 行第 列格子上积雪的相对高度。

对于所有数据,保证它们的 之和不超过

输出格式

对于每组测试数据,输出一行一个整数,表示小 w 完成目标需要的最小代价。

样例

样例输入 1

3
1 1
5
1 2
1 -1
2 2
-1 0
1 1

样例输出 1

5
0
3