Jerry’s Metro Journey

Jerry Prince, a fourth-grade student, plans to visit the famous amusement park The World's Start in New-Lodnon. The metro line in New-Lodnon has \(n\) stops with the park at the last stop. Jerry starts at stop 1 (the airport) and must reach stop \(n\) in no more than \(t\) minutes.

To travel, Jerry must buy a travel card. Each travel card is characterized by its range \(r\) and its price \(p\). With a travel card of range \(r\), Jerry is allowed to travel at most \(r\) stops at once. More formally, if he enters the metro at stop \(i\), he may exit at any stop \(j\) where \(|i - j| \le r\). The travel time between adjacent stops is 1 minute. If Jerry exits at an intermediate stop \(i\) (i.e. \(1 < i < n\)), he needs an extra \(d_i\) minutes to exit and re-enter the metro. There is no extra time cost for entering the first stop or exiting at the last stop.

Given the delays at the intermediate stops and a list of available travel cards, help Jerry determine the minimum price among all travel cards that allow him to complete his journey from stop 1 to stop \(n\) within at most \(t\) minutes. If no travel card can achieve the journey within \(t\) minutes, output \(-1\).

Input Format: The input begins with three integers \(n\), \(t\), \(m\) representing the number of stops, the maximum allowed time (in minutes), and the number of available travel cards, respectively. The next line contains \(n-2\) integers \(d_2, d_3, \dots, d_{n-1}\), representing the extra delay (in minutes) required when exiting (and reentering) at stops 2 through \(n-1\). The following \(m\) lines each contain two integers \(r\) and \(p\): the range and the price of a travel card.

Output Format: Output a single integer indicating the minimum price of a travel card that allows Jerry to travel from stop 1 to stop \(n\) within \(t\) minutes. If no such travel card exists, output \(-1\).

inputFormat

The first line contains three space-separated integers: \(n\) (the number of stops), \(t\) (the time limit in minutes), and \(m\) (the number of travel cards).

The second line contains \(n-2\) space-separated integers: \(d_2, d_3, \dots, d_{n-1}\); these represent the extra delay (in minutes) at stops 2 through \(n-1\).

The next \(m\) lines each contain two space-separated integers \(r\) and \(p\), representing a travel card's range and price respectively.

outputFormat

Output a single integer: the minimum price among the travel cards that allow Jerry to reach stop \(n\) within \(t\) minutes. If no such card exists, output \(-1\).

sample

5 6 2
2 2 2
2 10
3 15

10