U377663 独木桥

小未来到了一个神奇的地方，这个地方有很多人在走独木桥，于是，他想到了一个问题……

有一个长为 $L$ 米的南北走向的独木桥，桥上有 $N$ 个人，每个人的方向只有南和北两种选择，我们用 $-1$ 表示南，$1$ 表示北。第 $0$ 秒时，第 $i$ 个人距离独木桥最南端的距离为 $s_i$ 米，当 $i \ne j$ 时，保证 $s_i \ne s_j$。 假设每个人的移动速度大小都是相同的，每个人每秒都会往自己当前的方向移动 $1$ 米。然而，由于独木桥非常窄，所以一旦有两个方向为一南一北的人相遇了，他们就会各自改变自己的方向。 小未想知道，所有人都离开独木桥需要多少秒？

输入共 $N + 2$ 行： 第一行，输入一个正整数，表示 $L$； 第二行，输入一个正整数，表示 $N$； 接下来的 $N$ 行，每行输入两个用空格分隔的整数，第 $i + 2$ 行的第一个整数为 $-1$ 或 $1$，表示第 $i$ 个人第 $0$ 秒时的方向，第二个整数表示 $s_i$。

输出一个整数，表示答案。

本题共有五组测试数据： * 对于前三组测试数据，满足 $1 \le N \le 5, 0 < s_i < L \le 10$； * 对于所有的测试数据，满足 $1 \le N \le 10^5, 0 < s_i < L \le 10^9$。