弹珠碰撞

题号：NC239211
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在一条长度为 $n$ 的线段上，有 $m$ 颗弹珠在匀速左右滚动，在 $1$ 单位时间内，每颗弹珠能滚动 $1$ 单位距离。第 $i$ 颗弹珠由两个参数 $d_i,p_i$ 描述， $d_i$ 是一个值为 $0$ 或 $1$ 的整数，表示弹珠初始向左滚动/向右滚动； $p_i$ 是一个 $1$ 到 $n$ 之间的正整数，表示弹珠初始从线段上 $p_i$ 位置出发。

由于只有一条线段，两颗滚动方向相反的弹珠位置重合的时候就会停滞 $1$ 单位时间不滚动，并交换两颗弹珠滚动的方向。需要注意的是，一颗弹珠可以反复发生碰撞，如果在停滞中受到碰撞，则停滞时间会累加。

如果一颗弹珠滚到了位置 $0$ 或位置 $n+1$ ，那么这颗弹珠就滚出了线段。请问最后一颗弹珠在什么时候滚出线段？可以证明所有弹珠都会在某个整数时刻滚出线段。

输入描述:

第一行，两个整数  ，分别表示线段长度和弹珠数量。

第二行， 个整数，第  个整数表示 。

第三行， 个整数，第  个整数表示 ，保证  两两不同。

，，。

输出描述:

一行一个整数，表示最后一颗弹珠滚出线段的时刻。

示例1

输入

复制

2 2
0 1
1 2

输出

复制

示例2

输入

复制

3 2
1 0
1 3

输出

复制