Katarina obožava da putuje i već je počela da pravi planove za ovo leto. Napravila je spisak sa n egzotičnih mesta koja bi volela da poseti. Za svako mesto poznato je koliko dana bi ona tamo ostala, to su vrednosti t_i, i pri tome za svako i ≠ j važi t_i ≠ t_j.

Katarina ima p prijatelja sa kojima može da putuje. Međutim, ne žele svi prijate i da idu na sva mesta, već postoji p parova brojeva b_i i e_i (1 ≤ b_i ≤ e_i ≤ n). Oni nam govore da i-ti prijatelj želi da ide samo na mesta sa rednim brojem j takvim da važi b_i ≤ j ≤ e_i.

Potrebno je pronaći koliko najviše dana Katarina može da provede na putovanjima, ako moraju da budu zadovoljeni sledeći uslovi:

• Katarina nigde ne može da putuje sama.
• Sa svakim prijateljem ona može da ide na najviše jedno mesto.
• Svako mesto ona može posetiti najviše jednom.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke se nalazi broj n (n ≤ 5.000), broj mesta. U sledećem redu nalazi se n brojeva razdvojenih razmacima, to su vrednosti t_i (1 ≤ t_i ≤ 100.000). Sledi red u kome se nalazi broj p (p ≤ 5.000), broj prijatelja. U svakom od narednih p redova nalaze se po dva broja, b_i i e_i.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U izlaznu datoteku treba upisati samo jedan broj, koliko najviše dana mogu trajati sva Katarinina putovanja zajedno.

Primer:

8
2 3 1 4 6 5 20 9
5
5 6
2 5
1 2
8 8
8 8

23

Objašnjenje.

Postoji 8 mesta, na prvom se ostaje 2 dana, na drugom 3 dana, itd. Katarina ima 5 prijatelja. Prvi prijatelj želi da ide na mesto 5 ili 6, drugi na neko od mesta 2, 3, 4 i 5, itd. Optimalno rešenje dobija se na primer ako sa prvim prijateljem ode na šesto mesto (5 dana), sa drugim na peto mesto (6 dana), sa trećim na drugo (3 dana), i sa petim na osmo mesto (9 dana). To ukupno daje 5 + 6 + 3 + 9 = 23 dana.

Napomena.

U 60% test primera biće n, p ≤ 1.000, a u 30% n, p ≤ 200.