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 \leq N \leq~ ~100000~.
Dòng tiếp theo là ~N~ số nguyên mô tả khối lượng cá trong từng ô, mỗi số ~\geq 1~ và ~\le~ ~100~.
Dòng tiếp theo là số tàu ~M~, ~1 \leq M \leq 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.
Sample Input 1
11
2 5 3 4 7 6 2 1 3 8 5
2
8 3
3 2
Sample Output 1
20
Sample Input 2
13
3 2 4 7 2 1 3 6 1 2 6 4 1
2
5 7
11 4
Sample Output 2
38
Sample Input 3
11
1 1 6 4 4 1 1 3 10 1 1
3
2 3
6 4
10 2
Sample Output 3
31
Comments
Có thể nói, đây là một bài toán hay và độc đáo.
Cảm ơn
bầu Đứcmọi người.From GieJack™ with love <3