好奇心宝贝

题目描述

道路，由人亲手所造。 酒与面包，靠劳作取得。 幼小的新芽舒展叶片， 于成堆魔药中抵抗困意。 多一点，再多一点时间， 再看看书的下一页。

苏芙比正在观察一群魔精的行动，这群魔精正在一根木棍上呈一列排开。木棍长度为 $n$，上面有 $m$ 只魔精，每只魔精一开始都有自己的朝向(要么朝左，要么朝右)。

由于魔精的智力不高，他们只会沿着自身朝着的方向做直线运动，每秒向前移动一个单位。如果一只魔精与另一只魔精碰上，他们会互相掉头，朝相反的方向前进。如果一只魔精走到木棍的端点，他就会掉下去。

苏芙比知道，木棍上总会有魔精掉下去，但她不知道所有魔精都掉下木棍需要多久，于是她想请你帮帮她计算出所有魔精掉下木棍的时间(最开始的时刻记为 $0$ 秒)。

输入格式

输入包含3行，第一行为2个整数 $n$ 和 $m$。表示木棍的长度和魔精数量。 第二行为 $m$ 个整数 $P_i$，表示第 $i$ 只魔精的初始位置。 第三行为一个长度为 $m$ 的字符串 $s$，$s_i = 0$ 表示第 $i$ 只魔精最开始朝左，反之朝右。

数据范围

$1 \le n \le 10^9$ $1 \le m \le 2 \times 10^5$ $1 \le P_i \le n$ $s_i \in \{0,1\}$

输出格式

一个整数，表示所有魔精掉下去的时刻。

样例 #1

样例输入 #1

5 3
1 3 4
100

样例输出 #1

5

提示

最开始，第一只魔精向右，另外两只魔精向左，我们依次将他们记为 $A,B,C$。

在第一秒后，$A$ 与 $B$在位置 $2$ 相撞，他们相互反向，此时$A,B$在位置 $2$，但是 $A$ 朝左，$B$ 朝右，而 $C$ 位于位置3，朝左。

在第二秒后，$A$ 移动到位置 $1$，$B$ 和 $C$ 在位置2和3之间相撞并反向，最后 $B$ 和 $C$ 任然分别位于位置 $2$ 和 $3$，但是此时 $B$ 朝左，$A$ 朝右。

第三秒后，$A$ 从木棍左端掉下去了，$B$ 向左移动到位置 $1$，$C$ 向右移动到位置 $4$ 。

第四秒后，$B$ 从木棍左端掉下去了，$C$ 向右移动到位置 $5$ 。

第五秒后，$C$ 从木棍右端掉下去了。