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

木棍的两端各有一个障碍物，一个位于最左侧，另一个位于最右侧。当蚂蚁撞上障碍物时，它也会立即掉头并继续移动。然而，障碍物并非坚不可摧。左侧的障碍物在受到 $a$ 次撞击后会破碎，右侧的障碍物在受到 $b$ 次撞击后会破碎。当蚂蚁穿过破碎的障碍物时，它会从木棍上掉落。注意，每个障碍物的撞击次数是独立计算的，且撞碎障碍物的那只蚂蚁也会掉头，并不会立即掉落。

请问经过多少秒后，所有蚂蚁都会从木棍上掉落？

输入格式

每个测试文件中仅包含一组测试数据。

第一行包含三个整数 $n, a$ 和 $b$ ($1 \le n \le 10^6, 1 \le a, b \le 10^9$)，分别表示蚂蚁的数量、撞碎左侧障碍物所需的次数以及撞碎右侧障碍物所需的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9, a_i < a_{i+1}$)，表示蚂蚁的初始位置。

第三行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($d_i \in \{0, 1\}$)。如果 $d_i = 0$，则第 $i$ 只蚂蚁初始面向左侧；否则，它面向右侧。

输出格式

输出一行，包含一个整数，表示所有蚂蚁从木棍上掉落所需的秒数。

样例

输入 1

2 2 4
2 3
0 1

输出 1

4000000001

说明

样例测试数据的过程解释如下：

• 时间 2：蚂蚁 1 撞击左侧障碍物，左侧撞击次数 1，右侧撞击次数 0
• 时间 999999998：蚂蚁 2 撞击右侧障碍物，左侧撞击次数 1，右侧撞击次数 1
• 时间 1000000000.5：蚂蚁 1 与蚂蚁 2 在距离左侧 999999998.5 单位处相遇，左侧撞击次数 1，右侧撞击次数 1
• 时间 1000000003：蚂蚁 2 撞击右侧障碍物，左侧撞击次数 1，右侧撞击次数 2
• 时间 1999999999：蚂蚁 1 撞击左侧障碍物，左侧撞击次数 2，右侧撞击次数 2
• 时间 2000000001.5：蚂蚁 1 与蚂蚁 2 在距离左侧 2.5 单位处相遇，左侧撞击次数 2，右侧撞击次数 2
• 时间 2000000004：蚂蚁 1 从左侧掉落，左侧撞击次数 2，右侧撞击次数 2
• 时间 3000000000：蚂蚁 2 撞击右侧障碍物，左侧撞击次数 2，右侧撞击次数 3
• 时间 4000000001：蚂蚁 2 从左侧掉落，左侧撞击次数 2，右侧撞击次数 3