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 iz datoteke leto.in.) 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 u datoteku leto.out.) 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.

#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

const int maxN = 5000;

typedef struct { int t, index; } Mesto;
bool compareMesta(Mesto const& m1, Mesto const& m2) {
    return (m1.t > m2.t);
}
typedef struct { int b, e, index; } Interval;
bool compareIntervali(Interval const& i1, Interval const& i2) {
    return (i1.e < i2.e) || (i1.e == i2.e && i1.b > i2.b);
}

int n, p;
Mesto mesta[maxN];
Interval intervali[maxN];

int res;

int intervaluDodeljen[maxN], tmp[maxN];

void ucitajPodatke() {
    freopen("leto.in", "r", stdin);
    scanf("%d", &n); 
    for (int i = 0; i < n; i++) {
        scanf("%d", &(mesta[i].t));
        mesta[i].index = i;
    }
    scanf("%d", &p);
    for (int i = 0; i < p; i++) {
        scanf("%d%d", &(intervali[i].b), &(intervali[i].e));    
        intervali[i].b--;
        intervali[i].e--;
    }
}

void sortirajMesta() {
    sort(mesta, mesta + n, compareMesta);
}
void sortirajIntervale() {
    sort(intervali, intervali + p, compareIntervali);
}

bool uIntervalu(int mesto, int interval) {
    return intervali[interval].b <= mesto && mesto <= intervali[interval].e;
}
     
int probajDaDodas(int mesto) {
    int interval = 0;
    while (interval < p) {
        tmp[interval] = intervaluDodeljen[interval];
        if (uIntervalu(mesto, interval))
            if (tmp[interval] == -1) {
               tmp[interval] = mesto;
               return interval;                  
            } 
            else if (tmp[interval] > mesto) {
                int pom = tmp[interval];
                tmp[interval] = mesto;
                mesto = pom;
            }
        interval++;      
    }
    return -1;
}
   
void resi() {
  for (int i = 0; i < p; i++)
    intervaluDodeljen[i] = -1;
    for (int i = 0; i < n; i++) {
    int dodatU = probajDaDodas(mesta[i].index);
    if (dodatU != -1) {
      res += mesta[i].t;
      for (int j = 0; j <= dodatU; j++)
        intervaluDodeljen[j] = tmp[j];
    }
    }
}
     
void sacuvajResenje() {    
    freopen("leto.out", "w", stdout);
    printf("%d\n", res);
}

int main() {
    ucitajPodatke();
    sortirajMesta();
    sortirajIntervale();

    resi();
    sacuvajResenje();

    return 0;
}