program name
    implicit none
    integer(8):: n,m
    integer(8),allocatable:: a(:),b(:),c(:),change(:)
    integer(8):: i,ci

    read*, n,m
    allocate(a(n), b(m), c(m))
    read*, a(:)

    do i=1_8, m
        read*, b(i), c(i)
    end do

    call merge_sort(a, 1_8, n)
    call double_sort(c,b, 1_8,m)

    do i=2,m
        b(i) = b(i)+b(i-1)
    end do

    allocate(change(n))
    change(:) = 0_8
    ci=1
    do i=1, m
    change(ci:min(b(i),n)) = c(i)
    ci = b(i)+1

    if(ci > n) exit
    end do

    do i=1,n
        a(i) = max(a(i),change(i))
    end do

    print*, sum(a)
contains
recursive subroutine double_sort(ar1, ar2, fst, lst)
    integer(8),intent(inout):: ar1(:),ar2(:)
    integer(8),intent(in):: fst,lst
    integer(8):: mdl

    if (lst - fst < 2) then
        if (ar1(fst) < ar1(lst)) then
            call swap(ar1(fst), ar1(lst))
            call swap(ar2(fst), ar2(lst))
        end if
        return
    end if

    mdl = (fst+lst)/2

    call double_sort(ar1,ar2,fst,mdl)
    call double_sort(ar1,ar2,mdl+1,lst)
    call double_merge_(ar1,ar2,fst,mdl,lst)
end subroutine


subroutine double_merge_(ar1,ar2,fst,mdl,lst)
    integer(8),intent(inout):: ar1(:),ar2(:)
    integer(8),intent(in):: fst,mdl,lst
    integer(8),allocatable:: t1(:),t2(:)
    integer(8):: li,ri,ti

    allocate(t1(lst-fst+1), t2(lst-fst+1))

    li=fst
    ri=mdl+1
    ti=1

    do while(li <= mdl .and. ri <= lst)
        if (ar1(li) >= ar1(ri)) then
            t1(ti) = ar1(li) 
            t2(ti) = ar2(li)
            li=li+1
        else
            t1(ti) = ar1(ri)
            t2(ti) = ar2(ri)
            ri=ri+1
        end if
        ti=ti+1
    end do

    if (li <= mdl) then
        t1(ti:) = ar1(li:mdl)
        t2(ti:) = ar2(li:mdl)
    else
        t1(ti:) = ar1(ri:lst)
        t2(ti:) = ar2(ri:lst)
    end if

    ar1(fst:lst) = t1(:)
    ar2(fst:lst) = t2(:)

    deallocate(t1,t2)
end subroutine


recursive subroutine merge_sort(ar, fst, lst)
    integer(8),intent(inout):: ar(:)
    integer(8),intent(in):: fst,lst
    integer(8):: mdl

    if (lst-fst < 2) then
        if (ar(fst) > ar(lst)) call swap(ar(fst),ar(lst))
        return
    end if

    mdl = (fst+lst)/2
    call merge_sort(ar, fst, mdl)
    call merge_sort(ar, mdl+1, lst)
    call merge_(ar, fst, mdl, lst)
end subroutine

subroutine merge_(ar, fst, mdl, lst)
    integer(8),intent(inout):: ar(:)
    integer(8),intent(in):: fst, mdl, lst
    integer(8),allocatable:: tmp(:)
    integer(8):: li, ri, ti

    allocate(tmp(lst-fst+1))

    li=fst
    ri=mdl+1   
    ti=1

    do while (li <= mdl .and. ri <= lst)
        if (ar(li) <= ar(ri)) then
            tmp(ti) = ar(li)
            li=li+1
        else
            tmp(ti) = ar(ri)
            ri=ri+1
        end if
        ti=ti+1
    end do

    if (li <= mdl) then
        tmp(ti:) = ar(li:mdl)
    else
        tmp(ti:) = ar(ri:lst)
    end if

    ar(fst:lst) = tmp(:)
    deallocate(tmp)
end subroutine

subroutine swap(x,y)
    integer(8),intent(inout):: x,y
    integer(8):: tmp
    tmp = x
    x = y
    y = tmp
end subroutine
end program name