Ants on a Branch
There are $$$N$$$ ants on a straight branch of length $$$L$$$ meters. Each ant is at some initial position $$$p_i$$$ $$$(0 \leq p_i \leq L)$$$ and faces either left or right.
Every second, each ant moves exactly one meter in its current direction. If two ants collide, they both instantly reverse direction.
An ant falls off the branch if it reaches either end (position $$$0$$$ or $$$L$$$). Find the time (in seconds) when the last ant falls off the branch.
Input Format:
The first line contains two integers $$$N$$$ and $$$L$$$ $$$(1 \leq N \leq 2 \cdot 10^5, \; 1 \leq L \leq 10^9)$$$ — the number of ants and the length of the branch.
The second line contains $$$N$$$ integers $$$p_1, p_2, \ldots, p_N$$$ $$$(0 \leq p_i \leq L)$$$ — the initial positions of the ants.
The third line contains $$$N$$$ integers $$$d_1, d_2, \ldots, d_N$$$ where $$$d_i \in \{0,1\}$$$, representing the initial directions of the ants:
- $$$0$$$ means the $$$i$$$-th ant is facing left,
- $$$1$$$ means the $$$i$$$-th ant is facing right.
Output Format:
Print a single integer — the time when the last ant falls off the branch.
Examples:
Example 1:
Input:
4 4 0 1 2 3 1 1 0 1
Output:
4
Example 2:
Input:
5 4 0 1 2 3 4 1 1 1 1 1
Output:
4
Note:
TestCase:1 
TestCase:2 