Courier

As Christmas approaches, Bitlandia's parcel company Bitzon has an unusually large amount of work.

Bitlandia has $N$ cities connected by a single common highway. Bitzon's warehouse sits to the east of the first city. The distance from the warehouse to the first city is $m_1$ time units, from the first city to the second is $m_2$ time units, and so on, so that the cities line up in a row as shown below.

Every day a pile of parcels arrives at the warehouse for the courier to deliver. Each parcel is given an address (a city number) and a time by which it must be delivered. The courier may deliver a parcel earlier than its deadline, but must never deliver it later than the specified time.

The courier leaves the warehouse in the morning (we take this moment as time $0$) and drives back and forth between cities along the highway, delivering parcels.

In this problem, delivering a parcel is assumed to take no time; only driving from one city to another consumes time.

Given the list of parcels the courier must deliver, find:

1. Whether the courier can deliver all parcels without being late.
2. The minimum time needed to deliver all parcels and return to the warehouse.

The first line contains the number of cities $N$. The second line contains $N$ integers $m_1, m_2, \dots, m_N$, where $m_1$ is the distance from the warehouse to city 1 and, for $i \ge 2$, $m_i$ is the distance from city $i-1$ to city $i$. The third line contains the number of parcels $K$.

The following $K$ lines describe the parcels. Each line contains two integers: the city number $a_i$ ($1 \le a_i \le N$) where the parcel must be delivered, and the latest possible delivery time $t_i$.

The courier leaves the warehouse at time $0$. More than one parcel may be delivered to the same city. The courier may deliver the parcels in any order (as long as none is late).

Print a single integer: the minimum time in which it is possible to deliver all parcels and return to the warehouse. If at least one parcel cannot be delivered on time, print $-1$.

• $1 \le N \le 10,000$
• $1 \le m_i \le 100$
• $1 \le K \le 1000$
• $1 \le t_i \le 1,000,000$