택배 기사

크리스마스가 다가오면서, 비트란디아의 택배 회사 Bitzon은 평소보다 훨씬 많은 일을 처리해야 합니다.

비트란디아에는 하나의 고속도로로 연결된 $N$개의 도시가 있습니다. 1번 도시의 동쪽에 Bitzon의 물류 창고가 있습니다. 창고에서 1번 도시까지의 거리는 $m_1$ 시간 단위, 1번 도시에서 2번 도시까지는 $m_2$ 시간 단위이며, 아래 그림처럼 도시들이 한 줄로 이어집니다.

매일 창고에는 배송해야 할 많은 택배가 도착하고, 택배 기사가 이를 배달해야 합니다. 각 택배에는 배송 주소(도시 번호)와 배송을 마쳐야 하는 시각이 지정되어 있습니다. 택배 기사는 지정된 시각보다 일찍 배송할 수는 있지만, 지정된 시각보다 늦게 배송해서는 안 됩니다.

택배 기사는 아침에 창고에서 출발하며(이 순간을 시각 $0$으로 둡니다), 고속도로를 따라 도시 사이를 오가며 택배를 배송합니다.

이 문제에서는 택배를 전달하는 데 걸리는 시간은 $0$으로 간주하고, 한 도시에서 다른 도시로 이동하는 시간만 고려합니다.

배송해야 할 택배 목록이 주어질 때 다음을 구하세요.

1. 택배 기사가 모든 택배를 늦지 않게 배송할 수 있는지 여부.
2. 모든 택배를 배송하고 창고로 돌아오는 데 필요한 최소 시간.

첫째 줄에 도시의 수 $N$이 주어집니다. 둘째 줄에는 $N$개의 정수 $m_1, m_2, \dots, m_N$이 주어집니다. 여기서 $m_1$은 창고에서 1번 도시까지의 거리이고, $i \ge 2$인 경우 $m_i$는 $i-1$번 도시에서 $i$번 도시까지의 거리입니다. 셋째 줄에는 택배의 수 $K$가 주어집니다.

이어지는 $K$개의 줄에는 각 택배의 정보가 주어집니다. 각 줄에는 두 정수, 택배를 배송할 도시 번호 $a_i$ ($1 \le a_i \le N$)와 배송이 가능한 가장 늦은 시각 $t_i$가 주어집니다.

택배 기사는 시각 $0$에 창고에서 출발합니다. 같은 도시로 두 개 이상의 택배가 배송될 수 있습니다. 택배 기사는 (늦지 않는 한) 어떤 순서로든 택배를 배송할 수 있습니다.

모든 택배를 배송하고 창고로 돌아오는 데 필요한 최소 시간을 정수 하나로 출력하세요. 만약 단 하나의 택배라도 제시간에 배송할 수 없다면 $-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$