题目描述

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

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

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

木棍的两端各有一块挡板，左右两边的挡板的耐久分别为 $a$ 和 $b$，如果一只魔精走到木棍的端点，则会撞到挡板并掉头，此时挡板的耐久会-1。当一侧的挡板的耐久归零时，魔精就会从这一端掉下去。

注意，当魔精在撞到耐久为1的挡板时，此时挡板碎掉，而它会正常掉头。

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

温馨提示：本题的输入数据量很大，请采用高效地输入处理方法。

输入格式

输入包含3行，第一行为4个整数 $L,n,a,b$ 。表示木棍的长度,魔精数量,左右两边挡板的耐久。

第二行为 $m$ 个整数 $P_i$，表示第 $i$ 只魔精的初始位置。

第三行为一个长度为 $m$ 的01字符串 $s$，$s_i = 0$ 表示第 $i$ 只魔精最开始朝左，反之朝右。

数据范围

$1 \le L \le 2 \times 10^9$

$1 \le n \le 10^6$

$1 \le P_i \le L$

$P_i < P_{i+1}$

$s_i \in \{0,1\}$

输出格式

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

样例 #1

样例输入 #1

1000000001 2 2 4
2 3
01

样例输出 #1

4000000001

Note

样例解释：