Problem M: 农夫打狼

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $361$ 正确数量 $44$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划 动态规划 递推

小明是某RTS游戏的狂热爱好者,但是他从来不好好打游戏,经常搞出一些令人窒息的操作。一次,他竟然将自己的一个农夫派出去打野狼。

农夫初始时站在地图坐标(0,0)的位置,地图的出口的坐标为(n,n),地图上共有m只野狼,每只野狼有一个坐标(xi,yi),数据保证不会有两个野狼在相同的位置。农夫只有消灭地图上所有的野狼才能完成任务

整个地图y轴一共分为n层,当且仅当农夫清掉了本层的所有怪物之后才能到下一层,比如说,如果农夫当前的位置是(x,3,那么他必须将y坐标等于3的所有野狼消灭,才允许走到(x,4)。如果本层没有怪物,农夫能够直接到下一层。

由于小明使用的种族是Magyar,这个种族骁勇善战农夫只需一击就能将野狼打死。因而,每到一个位置,如果这个位置有野狼,他可以直接将怪物秒掉(不需要任何操作)。

现在给出m个野狼的坐标,问农夫最少需要走多少步才能完成任务农夫向上下左右移动一格算一步。 

第一行两个数n,m(n,m<=100,000)。 接下来m行,每行两个数,代表第i只野狼的坐标。
第一行两个数n,m(n,m<=100,000)。 接下来m行,每行两个数,代表第i只野狼的坐标。
4 5
1 1
2 1
1 2
3 2
3 3
10