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: def comb(n, r):
      if n - r < r:
          r = n - r
      if r == 0:
          return 1
      if r == 1:
          return n
  
      numerator = [n - r + k + 1 for k in range(r)]
      denominator = [k + 1 for k in range(r)]
  
      for p in range(2, r + 1):
          pivot = denominator[p - 1]
          if pivot > 1:
              offset = (n - r) % p
              for k in range(p - 1, r, p):
                  numerator[k - offset] /= pivot
                  denominator[k] /= pivot
  
      result = 1
      for k in range(r):
          if numerator[k] > 1:
              result *= int(numerator[k])
  
      return result
  
  
  N, M, K = map(int, input().split())
  
  C = comb(N * M - 2, K - 2)
  # print(int(C))
  
  A = int(0)
  for d in range(N):
      a = (N - d) * (M**2)
  
      A += int(d * a)
  
  B = int(0)
  for d in range(M):
      b = (M - d) * (N**2)
      B += int(d * b)
  
  ans = int((A + B) * C)
  ans = ans % (1000000007)
  print(ans)
  
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."}]