問題
長さ w の棒があります。
その上を、 n 匹のアリが左向き、または右向きに、時間が 1 進むごとに 1 進んでいきます。
アリ同士がぶつかると、反対方向を向いて歩き出します。
棒の両端へたどり着くと、次に進んだとき、アリは地面に落ちます。
全てのアリが地面に落ちるまでにかかる時間を求めてください。
入力
w n a0 x0 a1 x1 : : an-1 xn-1
1 行目には、棒の長さ w と、アリの数 n が与えられる。
2 行目以降には、アリの向いている方向が与えられる。
ai はアリの向きを表す。1 が右向き、2 が左向きを表す。
xi はアリのいる位置を表す。
出力
全てのアリが地面に落ちるまでの時間を 1 行で出力。
改行をわすれないように！！
制約
- 10 ≦ w ≦ 105
- 3 ≦ n ≦ w
- a : 1 or 2
- 0 ≦ x ≦ w - 1
入出力例
入力例
10 5 1 1 2 3 1 4 1 6 2 8
出力例
9