题目链接

题意

有一根绳子，长度为 $n$ ，上面有 $m$ 只虫子，每只虫子有一个坐标和一个移动方向，保证虫子的坐标两两不相同。虫子都做匀速运动，且运动速度都是每秒一单位长度。

如果两个方向不同的虫子相遇，他们会停止一秒，然后交换方向继续前进。

如果一只虫子到达了 $0$ 或 $n+1$ 的位置，那么它就离开了绳子。

求最后一只虫子离开绳子的时间。

输入格式

第一行两个整数 $n,m$。

第二行 $m$ 个整数，表示虫子的方向，$0$ 表示左，$1$ 表示右。

第三行 $m$ 个整数，表示每只虫子的开始坐标。

输出格式

一行一个整数，表示答案。

样例

2 2
0 1
1 2

1

3 2
1 0
1 3

4

数据范围

$1\le n,m\le 10^6$