题目描述

有 $n$ 只蚂蚁生活在一根长度为 $10^9 + 1$ 单位的木棍上。第 $i$ 只蚂蚁的初始位置距离木棍左端 $a_i$ 个单位。初始时，一些蚂蚁面向左，而另一些蚂蚁面向右。所有蚂蚁以每秒 $1$ 单位的速度朝它们面向的方向移动。当两只蚂蚁在同一点相遇时，它们会立刻掉头继续移动。

木棍的两端分别有一个障碍物：左端障碍物和右端障碍物。当蚂蚁撞上一个障碍物时，它会立刻掉头继续移动。然而，这些障碍物并非坚不可摧：

• 左端障碍物在被撞击 $a$ 次后会损坏；

• 右端障碍物在被撞击 $b$ 次后会损坏。

障碍物损坏后，蚂蚁可以穿过它并从木棍上掉落。需要注意的是，每个障碍物的撞击次数是独立计算的。此外，损坏障碍物的蚂蚁会先掉头一次，然后继续移动，不会立即掉落。

请计算，所有蚂蚁从木棍上掉落需要多少秒。

输入格式

第一行三个整数 $n, a, b$，分别表示蚂蚁的数量、左端障碍物的最大承受撞击次数和右端障碍物的最大承受撞击次数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示蚂蚁的初始位置。

第三行 $n$ 个整数 $d_1, d_2, \dots, d_n$，如果 $d_i = 0$，表示第 $i$ 只蚂蚁初始时面向左；如果 $d_i = 1$，表示第 $i$ 只蚂蚁初始时面向右。

输出格式

一行一个整数表示答案。

输入样例

2 2 4
2 3
0 1

输出样例

4000000001

说明提示

输入样例 #2

1 235163605 677343258
768729278
0

输出样例 #2

470327211239056488

输入样例 #3

2 277081811 982370412
311955673 708039233
1 1

输出样例 #3

277081813569042581

数据范围

对于 $30\%$ 的数据，$1\leq a,b\leq 10$。

对于另外 $20\%$ 的数据，$1\leq a,b\leq n$。

对于另外 $20\%$ 的数据，$d_i=0$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq a, b \leq 10^9$，$1 \leq a_i \leq 10^9$，$a_i < a_{i+1}$，$d_i\in\{0,1\}$。