      MODULE intQsortMod
! 整数型のクイックソート
! precisionで整数の精度を定める．
! インデックスの小さいほうが値も小さい(昇順)．

! 参考
! https://t.doujin-constant.net/post/143374686394/fortranをより使いこなしたquick-sort

      implicit none
      integer,parameter,private :: precision = 16
      
      interface qSort
        module procedure :: intQsort
      end interface
      
      contains
      pure recursive function intQsort( a ) result( r )
        implicit none
        integer(precision), intent(in) :: a(:)
        integer(precision) :: r( size(a) )
        integer(precision) :: sample(3), len, i,j
        
        len = size( a(:) )
        if( len<=1 )then
          r = a
        else
          !select pivot
          sample(1:3) = [a(1), a(len/2), a(len)]
          do i = 1,2
            do j = 2,3
              if( sample(i)>sample(j) )then
                len = sample(i) !len is buffer
                sample(i) = sample(j)
                sample(j) = len
              end if
            end do
          end do
          
          r = [ qSort( pack(a(:), a(:)< sample(2) ) ), &
                       pack(a(:), a(:)==sample(2) )  , &
                qSort( pack(a(:), a(:)> sample(2) ) ) ]
        end if
      end function intQsort
      END MODULE intQsortMod

      PROGRAM integerCards
      use intQsortMod
      IMPLICIT NONE
      integer(16) :: n,m
      integer(16),allocatable :: a(:),b(:),c(:),buffer(:)
      integer(16) :: i,j, L,R, current,next, numSwap
      
      read*,n,m
      allocate( a(n), b(m),c(m), buffer(n) )
      read*,a(1:n)
      do i = 1,m
        read*,b(i),c(i)
      end do
      
      a = qsort( a )
      
      do j = 1,m
        if( c(j)<=a(1) ) cycle
        
        L = 1; R = n
        current = (L+R)/2
        do while( .true. )
          if( a(current)>=c(j) )then
            R = current
          else
            L = current
          end if
          next = (L+R)/2
          if( next==current ) exit
          current = next
        end do
        
        numSwap = b(j)
        if( current<b(j) ) numSwap = current
        
        a(1:numSwap) = a(current-numSwap+1:current)
        a(current-numSwap+1:current) = c(j)
      end do
      
      print*,sum(a)
      
      
    !  print*,''
    !  print*,n,m
    !  print*,a(1:n)
    !  do i = 1,m
    !    print*,b(i),c(i)
    !  end do
      
      END PROGRAM