output_description: Print the maximum possible sum of the integers written on the N cards after
  the M operations.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 A_2 ... A_N
      B_1 C_1
      B_2 C_2
      \vdots
      B_M C_M
attempt: BC = {}
  N, M = input().split(" ")
  A = [int(x) for x in input().split(" ")]
  for m in range(int(M)):
      B, C = input().split(" ")
      if int(C) in BC.keys():
          BC[int(C)] = int(B) + BC[int(C)]
      else:
          BC[int(C)] = int(B)
      # print(BC)
  # A.sort(reverse=True)
  bc = list(BC.keys())
  # bc.sort(reverse=True)
  A.extend(bc)
  A.sort(reverse=True)
  S = 0
  nn = 0
  print(A)
  # while (nn < int(N)):
  for n in range(int(N)):
      if A[n] in bc:
          s = BC[A[n]]  # copy.deepcopy(BC[A[n]])
          bc.remove(A[n])
          if nn + s > int(N):
              S += (int(N) - nn - 1) * A[n]
          else:
              S += s * A[n]
      else:
          s = 1
          S += A[n]
      print("n{}, A[n]{}, nn{}, s{}".format(n, A[n], nn, s))
      nn += s
      if nn >= int(N):
          break
  print(S)
  
problem_description: Statement
  
  You have N cards. On the i-th card, an integer A_i is written.
  
  For each j = 1, 2, ..., M in this order, you will perform the following
  operation once:
  
  Operation: Choose at most B_j cards (possibly zero). Replace the integer
  written on each chosen card with C_j.
  
  Find the maximum possible sum of the integers written on the N cards after the
  M operations.
samples: [{"input": "3 2\n    5 1 4\n    2 3\n    1 5", "output": "14\n    \n\nBy replacing the integer on the second card with 5, the sum of the integers\nwritten on the three cards becomes 5 + 5 + 4 = 14, which is the maximum\nresult.\n\n* * *"}, {"input": "10 3\n    1 8 5 7 100 4 52 33 13 5\n    3 10\n    4 30\n    1 4", "output": "338\n    \n\n* * *"}, {"input": "3 2\n    100 100 100\n    3 99\n    3 99", "output": "300\n    \n\n* * *"}, {"input": "11 3\n    1 1 1 1 1 1 1 1 1 1 1\n    3 1000000000\n    4 1000000000\n    3 1000000000", "output": "10000000001\n    \n\nThe output may not fit into a 32-bit integer type."}]