题目描述

题目译自 Ukrainian Olympiads in Informatics 2018 Stage 4 Day2 T2. Автобусні маршрути

在尼古拉耶夫的新郊区，该区域呈矩形，所有道路要么严格从南到北，要么严格从西到东。因此，任意两条道路要么相互平行，要么相互垂直并在一个路口相交。整个郊区共有 $N$ 条水平道路和 $M$ 条垂直道路，因此总共有 $N \cdot M$ 个路口。

目前正在为该郊区设计公交线路方案。所有线路必须从地图左下角的路口开始，并在右上角的路口结束。此外，公交车在起点和终点之间必须沿着最短路径行驶，即总是向北或向东行驶（但在路径上的任意路口，公交车可以从向北转向向东，或从向东转向向北）。某些路口可能是重要路口：它们位于人口密集区域附近，必须至少有一条公交线路经过这些路口。

你的任务是规划一条公交线路网络，使得每个重要路口至少有一条线路经过，同时使总线路数量尽可能少。

输入格式

输入文件的第一行包含两个自然数：郊区的水平道路数量 $N$ 和垂直道路数量 $M$。已知 $2 \leq N \leq M \leq 1000$。接下来的 $N$ 行，每行包含 $M$ 个数字，表示对应的路口：数字 $1$ 表示该路口是重要的，数字 $0$ 表示该路口不是重要的。

输出格式

输出文件应包含一个非负整数，即从左下角路口到右上角路口的最短路径上可以规划的最小线路数量，同时确保覆盖所有重要路口。

3 4
0010
0101
1001

2

一条线路可以沿南部道路向东行驶，然后沿东部道路向北行驶。另一条线路可以按如下方式行驶：先向北到第一个转弯处，然后向东，再次向北，最后再向东经过两个路口。

数据范围与提示

详细子任务附加限制及分值如下表所示：