Ships on a River

Mirko invented a game played on a river divided into N fields, numbered from 1 to N from left to right. For each field, the amount of fish in that part of the river is known.

There are M ships. Each ship has a fixed length, so it occupies that many consecutive fields. For each ship, one anchor field is specified, and the ship must be placed so that this field is one of the fields it occupies.

No field may be occupied by more than one ship. The total amount of fish caught is the sum of fish in all fields occupied by ships.

Place every ship so that the total amount of fish caught is as large as possible.

The first line contains an integer N, the number of fields on the board, where 1 <= N <= 100000.

The second line contains N integers separated by spaces. The i-th integer is the amount of fish in field i, in kilograms. Each amount is between 1 and 100, inclusive.

The next line contains an integer M, the number of ships, where 1 <= M <= N.

Each of the next M lines contains two integers B and D. The ship on that line must include field B as its anchor field, and its length is D.

The input is guaranteed to have at least one valid placement for all ships.

Print one integer: the maximum possible total amount of fish caught.