SP7588 MISERMAN - Wise And Miser

杰克是一位聪明而节俭的人，他总是想办法省钱。 有一天，他计划从城市 A 前往城市 B。在 A 和 B 之间，共有 $N$ 个城市（包括 B，不包括 A），每个城市都有 $M$ 辆编号从 1 到 $M$ 的公交车。每辆公交车的票价可能不同，所以在这些 $N \times M$ 辆车中，每辆车的票价 $K$ 可能相同，也可能不同。杰克需要从城市 A 到达城市 B，并必须遵循以下规则： 1. 他必须在每个城市换乘公交车。 2. 他只能换乘到与前一辆车编号相同、或者编号小 1 或大 1 的公交车。 现在，请你帮助杰克用最少的车费，从 A 城市到达 B 城市。

第一行：两个正整数 $N$ 和 $M$。 接下来的 $N$ 行：一个 $N \times M$ 的网格，网格中的每一行代表从当前城市到下一个城市的 $M$ 辆公交车的票价。

一行，包含杰克从城市 A 到城市 B 需要支付的最小总票价。 **本翻译由 AI 自动生成**