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

    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)
    cl = sum(b)
    allocate(change(cl))
    change(:) = 0_8
    j=1
    do i=1,m
        change(j:j+b(i)-1) = c(i)
        j=j+b(i)
    end do

    call merge_sort(change, 1_8, cl)

    do i=1,min(cl,n)
        a(i) = max(a(i), change(cl-i+1))
    end do

    print*, sum(a)

contains
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