蛋仔真好玩

对于一个蛋仔狂热者,我还是十分喜欢里面的创意工坊的,因为在里面可以

众所周知，蛋仔非常的好玩（确信），其中有一个功能是创意工坊，这个功能是可以玩家自己创建一个地图来供大家游玩。 其中有一个图十分的有意思： 这个图类似于赛车类游戏中的跑圈竞技：也就是地图是一个圈，你的起点也是你的终点， 有的图需要你跑好几圈才能完成：于是两者融合就有了下面这个图 这个图也是一个跑圈图，对于这个图：首先他是的起点就是他的终点，如果简单的是一个跑圈图那么作者会感觉灰常的没意思，于是他加了一个好玩的东西

1. 我们假设该图是一个矩阵$a[n][m]$ n表示这张图的宽度,m表示这张图的长度
2. 在图中会有一些滚筒障碍物,这些障碍物当你每跑完一圈就会向上移动一次,等到该障碍物碰到边缘时 $a[n-1][j]$, 他的下一步会移动到 $a[0][j]$
3. 蛋仔不能碰到障碍物,碰到的话就会被淘汰出局
4. 对于每一秒,蛋仔都要移动,否者就会被后面的机器人淘汰,蛋仔可以由 $a[i][j]$蹦到 $a[i][j+1]$ 花费 1 秒钟, 也可以使用飞扑技能(没有冷却) 可以让蛋仔从 $a[i][j]$移动到 $a[i+1][j+1]$或者$a[i-1][j+1]$ ,由于蛋仔的体型比较圆润,所以飞扑会消耗2 秒钟时间.
5. 比赛开始时,你可以选择在$a[0][0],a[1][0],a[2][0],a[3][0],a[4][0]$选择一个起始位置
6. 若蛋仔已经走到了$a[i][m-1]$,如果圈数足够的话他下一步会直接胜利,否者他会跳到第$a[j][0]$.

现在你知道了地图的宽度n和长度m,每一个障碍物的坐标(x~i~,y~i~),以及需要跑的圈数. 最快到达终点的时间为多少. n固定为5 ###输入 第一行两个整数m,num,num_block表示该图的长度,要跑的圈数,以及障碍物的个数. 接下来 num_block行,每行两个数(x~i~,y~i~)表示第i个障碍物对应的位置

###输出 一个整数 即完成的最小时间

样例输入1

5 1 1
1 1

样例输出1

5

样例解释

对于样例1,刚开始其可以选择在 $a[2][0]$出发; 第一秒他到达了 $a[2][1];$ 第二秒他到达了 $a[2][2];$ 第三秒他到达了 $a[2][3];$ 第四秒他到达了 $a[2][4];$ 第五秒因为他只需要走一圈,所以他的下一步会直接完成,没有比该方案更优的方案,所以答案为5

数据范围

对于$\%10$的数据: $2 <= m * num <= 10$

对于$\%40$的数据: $10 <= m * num <= 10^2$

对于$\%100$的数据: 一定可以到达终点. $5 <= m * num <= 10^6$

$2 <= m <= 1000$

$1 <= num <= 10000$

$0 <= num\_block <= m - 1$ 对于每一块障碍物 $0 <= x_i < n$

$1 <= y_i < m$

时间空间限制

1000ms , 256MB