题目描述

一条长度为 $n$ 厘米的小路上挤满了 $m$ 只蚂蚁，每只蚂蚁有一个初始的行走方向，它们的前进速度相同且均为 $1 cm/s$。

蚂蚁们想尽快离开这里。但小路十分狭窄，当两只蚂蚁相遇时，它们不得不掉头向着相反的方向前进。

如果要让所有的蚂蚁都离开小路（当蚂蚁走到 $0$ 或者 $n$ 即可视作离开了小路），最小需要多长时间？

输入格式

第一行有两个整数 $n,m,1≤m<n≤10^5$，分别代表小路的长度和蚂蚁的数量。

接下来 $m$ 行，每行 $2$ 个数，分别代表蚂蚁的初始方向（$0$ 代表向左，$1$ 代表向右）和初始位置 $x, 1\le x < n$。

保证蚂蚁的初始位置从小到大依次给出。

输出格式

一行一个整数，表示所有蚂蚁离开小路的时间。

样例 #1

样例输入 #1

50 10
1 6
0 15
0 19
1 20
0 22
0 25
1 36
0 39
1 40
1 42

样例输出 #1

44