MFISH - Catch Fish

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mfish


 

Hồi nhỏ, Mirko thích chơi "Bắn tàu" nhưng bây giờ anh ta chơi trò "Câu cá trên sông" “Sea battle”.

Trò chơi mô tả trên 1 bảng N ô đánh số từ 1 đến N từ trái qua phải. Trên đó sẽ đặt M tàu.  Với mỗi ô sẽ biết số lượng cá mà ở trong ô đó. Mỗi tàu sẽ chiếm 1 số ô liên tiếp và nó phải thả neo vào 1 ô nào đó.  Nghĩa là ta sẽ biết được với mỗi tàu, ô mà tàu đó bắt buộc phải chiếm.

Chỉ có thể có 1 tàu trên mỗi một ô. Lượng cá bắt được là tổng lượng cá nằm trong ô mà tàu này chiếm.  Cần bắt được nhiều cá nhất.

Bạn hãy giúp Mirko đặt tàu.

 

Input

 

Dòng đầu là số N, số ô, 1 ≤ N ≤ 100000.

Dòng tiếp theo là N số nguyên mô tả khối lượng cá trong từng ô, mỗi số >=1 và <=100.

Dòng tiếp theo là số tàu M,  1 ≤ M ≤ N.

M dòng tiếp theo, mỗi dòng gồm 2 số B và D, nghĩa là tàu phải thả neo ở ô B và tàu có độ dài là D ô.

 

Output

 

Khối lượng cá lớn nhất bắt được.

 

http://www.youtube.com/watch?v=c2D4XNQg3Zc&feature=related

Ban tau + danh ca lam nho den AOE ...

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


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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.