강 위의 배

미르코는 N개의 칸으로 나뉜 강에서 하는 게임을 만들었다. 칸은 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 붙어 있다. 각 칸에는 그 구간을 헤엄치는 물고기의 양이 주어진다.

강에는 M척의 배를 놓아야 한다. 각 배는 정해진 길이를 가지며, 그 길이만큼 연속한 칸을 차지한다. 또한 각 배마다 닻을 내려야 하는 칸이 하나 주어지며, 그 배가 차지하는 칸들 중 하나가 반드시 그 칸이어야 한다.

한 칸에는 배 또는 배의 일부가 둘 이상 놓일 수 없다. 잡은 물고기의 총량은 모든 배가 차지한 칸에 있는 물고기 양의 합이다.

모든 배를 놓았을 때 잡을 수 있는 물고기의 총량을 최대로 만들어라.

첫째 줄에 칸의 수 N이 주어진다. 1 <= N <= 100000이다.

둘째 줄에는 각 칸에 있는 물고기의 양을 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 수는 킬로그램 단위이며, 1 이상 100 이하이다.

다음 줄에는 배의 수 M이 주어진다. 1 <= M <= N이다.

이어지는 M개의 줄에는 두 정수 B와 D가 공백으로 구분되어 주어진다. 해당 배는 B번 칸을 닻을 내리는 칸으로 반드시 포함해야 하며, 배의 길이는 D이다.

입력은 모든 배를 놓을 수 있는 배치가 적어도 하나 존재하도록 주어진다.

잡을 수 있는 물고기 총량의 최댓값을 정수 하나로 출력한다.