#include <bits/stdc++.h>

using namespace std;

class segtree {
    struct node {
        int v = 0 ; // default value for the leafs
        int lazy = 0; // no lazy value

        inline void apply(int l, int r) {
            v = 0;
            // set v to the new value of range [l , r] when updated with x
        }

        inline void add_lazy() {
            lazy = 1;
            // lazy combine
        }

        inline node operator +(const node &other) const {
            node ret;
            ret.v = v + other.v;
            // combine v with other.v
            return ret;
        }

        inline bool isLazy() {return lazy == 1;}
        inline void cancel() {lazy = 0;}
    };

    inline void push(int l, int r, int p) {
        if (tree[p].isLazy()) {
            tree[p].apply(l, r);
            if (l != r) {
                tree[left(p)].add_lazy();
                tree[right(p)].add_lazy();
            }
            tree[p].cancel();
        }
    }

    inline int left(int p) { return p << 1; }
    inline int right(int p) { return (p << 1) + 1; }

    int n;
    vector<node> tree;

    void update(int s, int e , int l, int r, int p) {
        push(l, r, p);
        if (l > e || r < s)
            return;

        if (l >= s && r <= e) {
            tree[p].apply(l, r);
            if (l != r) {
                tree[left(p)].add_lazy();
                tree[right(p)].add_lazy();
            }
            return;
        }
        int mid = (l + r) >> 1;
        update(s, e , l, mid, left(p));
        update(s, e , mid + 1, r, right(p));
        tree[p] = tree[left(p)] + tree[right(p)];
    }

    void point_update(int i , int v , int l, int r, int p) {
        push(l , r , p);
        if (i > r || i < l)
            return;

        if (l == r) {
            tree[p].v += v;
            return;
        }

        int mid = (l + r) >> 1;
        point_update(i , v , l, mid, left(p));
        point_update(i , v ,  mid + 1, r, right(p));
        tree[p] = tree[left(p)] + tree[right(p)];
    }

    int get_kth(int k , int l , int r , int p) {
        push(l , r , p);
        if (l == r)
            return l;

        int mid = (l + r) >> 1;
        push(l , mid , p * 2);
        push(mid + 1 , r , p * 2 + 1);

        if (tree[p * 2].v >= k)
            return get_kth(k , l , mid , p * 2);

        return get_kth(k - tree[p * 2].v , mid + 1 , r , p * 2 + 1);
    }

    node query(int s , int e , int l , int r , int p) {
        push(l , r , p);
        if (l >= s && r <= e) return tree[p];
        int mid = (l + r) >> 1;
        if (e <= mid)
            return query(s , e , l , mid , left(p));
        else if (s > mid)
            return query(s , e , mid + 1 , r , right(p));
        return query(s , e , l , mid , left(p)) + query(s , e , mid + 1 , r , right(p));
    }

public:
    segtree(int _n) : n(_n) {tree.resize(4 * n);}

    void point_update(int p, int v) {
        point_update(p , v , 0, n - 1, 1);
    }

    void range_update(int s , int e) {
        update(s, e , 0, n - 1, 1);
    }

    int query(int s, int e) {
        if (e < s)
            return 0;
        return query(s, e, 0, n - 1, 1).v;
    }

    int get_kth(int k) {
        return get_kth(k , 0 , n - 1 , 1);
    }
};

int main() {
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

    int n , m;
    cin >> n >> m;

    map<int , int> New , Old;
    vector<int> a(n);
    for (int i = 0 ;i < n ;i++) {
        cin >> a[i];
        New[a[i]];
    }

    vector<pair<int , int> > q(m);
    for (int i = 0 ;i < m ;i++) {
        cin >> q[i].first >> q[i].second;
        New[q[i].second];
    }

    int sz = 0;
    for (auto &c : New) {
        c.second = sz;
        Old[sz++] = c.first;
    }

    segtree st(sz + 1);
    for (int i = 0 ;i < n ;i++) {
        a[i] = New[a[i]];
        st.point_update(a[i] , 1);
    }

//    for (int i = 0 ;i < sz ;i++)
//        cout << i << " " << Old[i] << " " << st.query(i , i) << endl;

//    cout << endl;

//    long long ans = 0;
//    for (int i = 0 ;i < sz ;i++)
//        ans += st.query(i , i) * 1ll * Old[i];

//    cout << ans << endl;

    for (int i = 0 ;i < m ;i++) {
        int cnt = q[i].first , new_card = New[q[i].second];
        int smaller = st.query(0 , new_card - 1);
//        cout << smaller << endl;
        if (cnt < smaller) {
            int largest = st.get_kth(cnt);
            int sub = cnt - st.query(0 , largest - 1);
//            cout << largest << " " << sub << endl;
            st.range_update(0 , largest - 1);
//            cout << st.query(0 , 0) << endl;
            st.point_update(largest , -sub);
//            cout << st.query(largest , largest) << endl;
            st.point_update(new_card , cnt);
//            cout << st.query(new_card , new_card) << endl;
        } else {
            st.range_update(0 , new_card - 1);
            st.point_update(new_card , smaller);
        }

//        cout << endl;
//        long long ans = 0;
//        for (int i = 0 ;i < sz ;i++) {
//            ans += st.query(i , i) * 1ll * Old[i];
//            cout << i << " " << Old[i] << " " << st.query(i , i) << endl;
//        }
//
//        cout << ans << endl;
    }

    long long ans = 0;
    for (int i = 0 ;i < sz ;i++)
        ans += st.query(i , i) * 1ll * Old[i];

    cout << ans;
}


Measured memory_bytes: 26496