"Zvejas kuģi" ir spēle ko spēlē uz N, vienu otrai sekojošu, rūtiņu rindas. Rūtiņas ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas no kreisās puses uz labo. Šīs rūtiņas attēlo upi, kurā jāizvieto M zvejas kuģi. Katrai upes rūtiņai ir zināms tajā peldošo zivju daudzums kilogramos. Katram zvejas kuģim ir noteikts garums, t.i. pēc kārtas sekojošo rūtiņu skaits, ko tas aizņem. Katram kuģim ir noteikta enkura vieta - viena fiksēta rūtiņa, kuru šis kuģis noteikti aizņem.

Katra rūtiņā var piederēt tikai vienam kuģim. Katra kuģa nozvejoto zivju daudzumu aprēķina kā visu šī kuģa aizņemto rūtiņu zivju daudzumu summu.

Uzrakstiet programmu, kas aprēķina lielāko iespējamo visu zvejas kuģu noķerto zivju kopējo daudzumu!

Ievaddatu pirmajā rindā dota naturāla skaitļa N (upi apzīmējošo rūtiņu skaits) vērtība (1≤N≤100000). Faila otrajā rindā doti N naturāli skaitļi, kas atdalīti ar tukšumsimboliem - katrā rūtiņā esošo zivju daudzums kilogramos. i-tais skaitlis rindā norāda zivju daudzumu i-tajā rūtiņā. Zivju daudzums katrā rūtiņā ir vismaz 1 un ne vairāk kā 15 kilogrami. Nākošajā faila rindā dota naturāla skaitļa M (zvejas kuģu skaits) vērtība, 1≤M≤N. Katrā no nākošajām M faila rindām dots pa diviem naturāliem skaitļiem B(kuģa enkura vieta) un D(kuģa garums), kas atdalīti ar tukšumsimboliem.

Ievaddati vienmēr ir tādi, ka atrisinājums eksistē. 

Izvaddatu vienīgajā rindā jāizvada viens naturāls skaitlis - lielākais iespējamais visu kuģu kopīgi noķertais zivju daudzums.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā