Ships on a River

Time limit1sMemory limit128 MB

Summary

Given river fields with fish amounts and ships each needing a fixed anchor field and length placed without overlap, maximize total fish covered.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Intervals
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
11
2 5 3 4 7 6 2 1 3 8 5
2
8 3
3 2
```
Expected output
```
20
```

Example 2

Input

13
3 2 4 7 2 1 3 6 1 2 6 4 1
2
5 7
11 4

Expected output

Example 3

Input

11
1 1 6 4 4 1 1 3 10 1 1
3
2 3
6 4
10 2

Expected output