Efficient Information Transmission on Mercury

On Mercury, there are $n$ servers arranged in a line, connected by $n-1$ bidirectional cables such that the $i$-th cable connects server $i$ and server $i+1$. When Earth sends a message to server $j$ at time $S$, that server immediately stores the message permanently and holds a copy in its buffer for $t_i$ seconds (for server $i$). Each server will forward the message at the first opportunity available after reception. However, due to external factors, the $i$-th cable can only transmit information during the time interval $[l_i, r_i]$. Specifically, when a cable becomes active, if one of its two connected servers still holds the message in its buffer (i.e. within its $t$-second retention period) then the other server instantaneously receives the message. In other words, if a server receives the message at time $T$, it will forward this message at time $\max\{T, l\}$ provided that [ \max{T, l} \le T+t_{\text{server}} \quad \text{and} \quad \max{T, l} \le r,. ] You are allowed to choose $S$ arbitrarily. Your goal is to ensure that, after the message is sent to server $j$, all servers eventually receive it. Output the minimum possible duration from the Earth sending time $S$ to the moment when the final server receives the message. If it is impossible to deliver the message to every server, output $-1$.

Input/Output Timing Note: The transmissions on a cable occur exactly at time $\max\{T, l_i\}$ (where $T$ is the sending server's reception time) if that time does not exceed both $T+t_{\text{server}}$ (the buffer expiry) and $r_i$ (the cable’s active window).

inputFormat

The first line contains two integers $n$ and $j$ ($1 \le j \le n$), representing the number of servers and the index of the server that first receives the message from Earth. The second line contains $n$ integers $t_1, t_2, \ldots, t_n$, where $t_i$ is the number of seconds that server $i$ retains the message in its buffer. Each of the following $n-1$ lines contains two integers $l_i$ and $r_i$, representing the active time interval of the $i$-th cable.

outputFormat

Output a single integer: the minimum possible duration from the Earth sending time to the moment when all servers have received the message, or $-1$ if it is impossible.

sample

3 2
3 3 3
1 5
2 6

0