Problem J
Up and Away Again

Steve’s Retreat

Another year has passed, and Steve wants to travel to his vacation house again! There are still $n$ bases located on mountains located around his house. Steve is located at mountain $1$ and his vacation house is at mountain $x$.

This year, the Biomes Ski Corporation has built many ski lifts between mountains. Steve wants to take the ski lifts hoping that he can get a more scenic trip than flying. Steve knows that each mountain has a danger level of $d_ i$, meaning that a mountain with a height of $h_ i$ is only connected via ski lift with a mountain of height $h_ j$ if $abs(h_ i - h_ j) \leq d_ j$. However, due to low budget, only ski lifts going downwards were built. Thus, from a mountain with height $h_ i$, he can only travel to mountains with a danger level of $d_ j$ and height of $h_ j$ if $0 \leq h_ i - h_ j \leq d_ j$.

Each ski lift operates with a time of $t$ between two mountains. Please help Steve figure out the minimum time needed to travel to his vacation house, or determine that he can’t reach his house using ski lifts!

Input

The first line contains $3$ space-separated integers $n$, $x$, and $t$ ($1 \leq n \leq 10^5, 1 \leq x \leq n, 1 \leq t \leq 10^9$), the number of bases, location of the vacation house, and time for each ski lift, respectively.

The second line contains $n$ integers $h_1, h_2, \ldots , h_ n$, where $h_ i$ ($1 \leq h_ i \leq 10^5$) is the height of the $i^{th}$ base’s mountain.

The third line contains $n$ integers $d_1, d_2, \ldots , d_ n$, where $d_ i$ ($1 \leq d_ i \leq 10^5$) is the danger level of the $i^{th}$ base’s mountain.

Output

Output a single integer that is the minimum time Steve needs to travel to his vacation house. Output -1 if he cannot reach his vacation house using ski lifts.

3 3 4
3 6 2
1 2 3

4