Codah ClubВежбај. Пошаљи. Напредуј.
Пријави се
Српски
#00065B

Leto - Državno

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 ti, i pri tome za svako i ≠ j važi ti ≠ tj.


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


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.


InputU prvom redu standardnog ulaza se nalazi broj n (n ≤ 5.000), broj mesta. U sledećem redu nalazi se n brojeva razdvojenih razmacima, to su vrednosti ti (1 ≤ ti ≤ 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, bi i ei.

OutputNa standardni izlaz treba ispisati samo jedan broj, koliko najviše dana mogu trajati sva Katarinina putovanja zajedno.

Ulaz:
8
2 3 1 4 6 5 20 9
5
5 6
2 5
1 2
8 8
8 8
Izlaz:
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.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.