MFISH - Catch Fish


 

During his childhood, Mirko liked to play “Sea battle” a lot, but once he got bored of it and invented a new game imaginatively called “Ships catch fish on a river”.

The game board consists of N fields lined up in a row and numbered 1 to N in ascending order from left to right. These fields represent a river on which M ships are to be placed. For each field the amount of fish swimming in that part of the river is known. Every ship has a specific length, i.e. it occupies the specific number of consecutive fields. A ship must somewhere drop an anchor but is allowed to do that in a certain field only. That means that one of the fields a ship will occupy is predetermined.

There can be only one ship or a part of only one ship on a single field of the board. We define the total amount of fish caught as the sum of amounts of fish swimming in all fields occupied by ships. Goal of the game is to place all ships on the river in a way that the total amount of fish caught is maximal.

While playing an instance of this game, Mirko is in doubt whether the way he placed ships is optimal. Therefore he asked you to help him calculate the maximum possible amount of fish caught.

 

Input

 

First line of the input file contains an integer N, the number of fields on board, 1 ≤ N ≤ 100000.

In the next line there are N integers, separated by whitespaces, which represent the amounts of fish swimming in appropriate field, given in kilograms. These numbers will not be less than 1 nor greater than 100.

The next line contains an integer M, number of the ships, 1 ≤ M ≤ N.

Each of the following M lines consists of two integers B and D separated by a whitespace. That means that the appropriate ship should drop the anchor in a field numbered with B and that its length is D.

Note: input data will always be such that the solution will exist

 

Output

 

The only line of the output file should contain the maximum possible total amount of fish caught.

 

Sample

brodovi.in 

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

brodovi.out

20

brodovi.in

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

brodovi.out

38

brodovi.in

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

brodovi.out

31


hide comments
bouhmid: 2018-05-18 14:31:17

aspro , your testcases are valid ?
the first shouldn't have 201 an answer ans the second 300 ?

babur: 2017-12-12 18:10:35

Learnt so much...dp at its best

mastik5h_1998: 2017-09-29 17:49:04

very nice problem....

aspro: 2017-05-31 07:20:08

try these test cases:
5 100 100 1 1 1 2 3 3 2 1 ,ans =103
5 1 1 100 100 100 2 3 3 4 1,ans= 202
these two cases cover most of concept needed to solve this ques.

hasan356: 2017-04-06 13:44:18

great problem !!

mykhivanov: 2016-08-25 23:16:45

Last edit: 2016-08-25 23:17:01
Márton Erdõs: 2015-09-26 15:38:30

Before you waste your time: read from stdin and write to stdout, instead of the files given :S
Otherwise it's a good problem.

birdie: 2015-08-24 12:44:48

Any tricky test cases?

nono: 2015-02-25 02:00:26

Last edit: 2015-02-26 20:20:20
Vaibhav Gosain: 2015-01-14 20:20:35

a tough one to crack...


Added by:~!(*(@*!@^&
Date:2009-05-04
Time limit:0.121s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 03