P14126 [SCCPC 2021] Ants

There are $n$ ants living on a stick of length $(10^9 + 1)$ units. The initial position of the $i$-th ant is $a_i$ units away from the left side of the stick. Some of the ants are facing left at the beginning, while the others are facing right. All ants will move at a speed of 1 unit per second in the direction they're facing. When two ants meet face to face at the same point, both of them will turn around instantly and move on. There are also two obstacles on the sides of the stick, one located on the leftmost and the other on the rightmost. When an ant runs into one of them, it will also turn around instantly and move on. However, the obstacles aren't indestructible. The left one will break after $a$ hits, while the right one will break for $b$ hits. After an ant passes through a broken obstacle it will fall from the stick. Note that the number of hits is calculated independently for each obstacle, and that the ant which breaks the obstacle will also turn around and will not fall immediately. In how many seconds will all ants fall from the stick?

There is only one test case in each test file. The first line of the input contains three integers $n$, $a$ and $b$ ($1 \le n \le 10^6$, $1 \le a, b \le 10^9$) indicating the number of ants, the number of hits to break the left obstacle and the number of hits to break the right obstacle. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$, $a_i < a_{i+1}$) indicating the initial position of ants. The third line contains $n$ integers $d_1, d_2, \cdots, d_n$ ($d_i \in \{0, 1\}$). If $d_i = 0$ then the $i$-th ant is facing left initially, otherwise it is facing right.

Output one line containing one integer indicating the number of seconds for all ants to fall from the stick.

$$ \begin{array}{|c|c|c|c|} \hline \textbf{Time} & \textbf{Event} & \textbf{Left Hit} & \textbf{Right Hit} \\ \hline 2 & \text{Ant 1 hits the left obstacle} & 1 & 0 \\ \hline 999999998 & \text{Ant 2 hits the right obstacle} & 1 & 1 \\ \hline 1000000000.5 & \text{Ant 1 meets ant 2 at 999999998.5 units from the left} & 1 & 1 \\ \hline 1000000003 & \text{Ant 2 hits the right obstacle} & 1 & 2 \\ \hline 1999999999 & \text{Ant 1 hits the left obstacle} & 2 & 2 \\ \hline 2000000001.5 & \text{Ant 1 meets ant 2 at 2.5 units from the left} & 2 & 2 \\ \hline 2000000004 & \text{Ant 1 falls from the left} & 2 & 2 \\ \hline 3000000000 & \text{Ant 2 hits the right obstacle} & 2 & 3 \\ \hline 4000000001 & \text{Ant 2 falls from the left} & 2 & 3 \\ \hline \end{array} $$