Hide

# Problem JUp 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.

Sample Input 1 Sample Output 1
3 3 4
3 6 2
1 2 3
4