FRAKTAL - konkurs programistyczny

Po dorobieniu się, w nie do końca legalny sposób, dużych pieniędzy Jaś postanowił odpocząć na wakacjach. Kierunek - Birma.

Jasiowi bardzo zależy na zobaczeniu różnych atrakcji turystycznych tego egzotycznego kraju. Jako człowiek skrupulatny, chce bardzo dokładnie zaplanować cały pobyt.

Na pierwszy dzień wybrał stolicę. Znajduje się tam długa ulica, wzdłuż której stoją najróżniejsze świątynie, pałace, pomniki i galerie handlowe. Każdemu obiektowi Jaś przypisał liczbę, jak bardzo chciałby go zobaczyć. Liczba ta może być ujemna, co oznacza, że Jaś nie chce zwiedzać tego budynku. Nasz bohater zastanawia się teraz, jak wyznaczyć spójny odcinek ulicy, który będzie miał największą sumę poziomu atrakcyjności odwiedzonych budynków.

Jaś nie zamierza jednak pokonywać wybranej trasy pieszo. Chce pojechać rikszą, którą może wynająć w prawie każdym punkcie na ulicy. Każda riksza startuje z określonego punktu na ulicy i może pojechać pewną odległość k_i w górę lub dół ulicy (riksza może jechać tylko w jednym kierunku). Dla każdej rikszy wartość k_i może być inna. Rikszą można pojechać odcinek krótszy niż jej k_i (jest to maksymalny dystans, jaki można pokonać). Jaś może wybrać dowolną rikszę, pojechać w górę lub dół ulicy pewną odległość nie większa niż k_i, następnie wsiąść w rikszę jadącą w drugą stronę i wrócić do punktu startu. Wsiadając do rikszy w drodze powrotnej, Jaś musi się upewnić, że jest w stanie dojechać do punktu startu (tam planuje zarezerwować pokój w hotelu).

W każdym punkcie ulicy mogą być maksymalnie dwie riksze. Jedna jadąca w górę ulicy, druga w dół.

Ostatecznie Jaś przejedzie wybrany odcinek ulicy dwa razy, jednak oglądanie tej samej atrakcji turystycznej po raz drugi nie robi już takiego wrażenia, więc poziom atrakcyjności liczymy tylko raz.

Wyznacz największą możliwą sumę atrakcyjności odwiedzonych w taki sposób atrakcji turystycznych.

Wejście

Na wejściu znajduje się liczba n (0 < n ≤ 10⁵), czyli ilość atrakcji turystycznych wzdłuż ulicy.

Następnie n wartości v_i (-10⁵ ≤ v_i ≤ 10⁵) oznaczających atrakcyjność danego obiektu. Dół ulicy reprezentują liczby po lewej stronie.

Kolejna jest liczba m (0 < m ≤ 2*n - 2) - ilość riksz dostępnych do wynajęcia.

W kolejnych m wierszach znajduje się opis każdej z rikszy. Opis zawiera dwie liczby p_i, k_i (0 < p_i ≤ n; k_i < 0 lub k_i > 0; |k_i|< n), czyli punkt startowy rikszy oraz maksymalny dystans na jaki może ona pojechać. Jeżeli k_i jest ujemne, to znaczy, że riksza jedzie w dół ulicy. Jeżeli k_i jest dodatnie - w górę ulicy. Wartość k_i dla danego p_i nigdy nie wychodzi poza zakres ulicy.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie: jaka jest największa suma atrakcyjności wybranego odcinka ulicy zwiedzanego w sposób opisany w zadaniu.

Jeżeli nie da się zorganizować wycieczki w taki sposób, wypisz: "nie da sie".

Przykład 1

Wejście:

6
-1 2 -2 5 -5 3
7
1 4
6 -1
3 -2
4 1
2 1
5 -4
5 1

Wyjście:

0

Przykład

Wejście:

7
1 2 3 4 5 6 7
3
2 5
4 -1
6 -2

Wyjście:

nie da sie

Wyjaśnienie pierwszego przykładu: 

Dostępne trasy to:

1->3, 3->1: suma: -1
1->5, 5->1: suma: -1
3->2, 2->3: suma: 0
4->5, 5->4: suma: 0
6->5, 5->6: suma: -2

Najlepszą opcją będzie przejazd od atrakcji 2 do 3 i z powrotem (lub od 3 do 2 i z powrotem, efekt będzie ten sam) lub od 4 do 5 atrakcji i z powrotem.