Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, m = map(int, input().split())
p = 10**9 + 7



def fac(n):
  x = 1
  for i in range(1,n+1):
    x *= i
  return x

nf = fac(n) % p
mf = fac(m) % p

if abs(n-m) > 1:
  ans = 0

elif n == m:
  ans = nf * mf * 2
  
else:
  ans = nf * mf
  
print(ans % p)

### FIXED CODE ###

import math
n, m = map(int, input().split())
p = 10**9 + 7



nf = math.factorial(n) % p
mf = math.factorial(m) % p

if abs(n-m) > 1:
  ans = 0

elif n == m:
  ans = nf * mf * 2
  
else:
  ans = nf * mf
  
print(ans % p)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())

    for i in range(Q):
        q = input()
        if len(q.split(' ')) > 1:
            T, F, C = q.split(' ')
            if F == '1':
                S = C + S
            elif F == '2':
                S = S + C
        elif q == '1':
            S = S[::-1]

    print(S)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    S = input()
    Q = int(input())

    t = deque(S)
    reverse = False
    for _ in range(Q):
        query = input()
        if query[0] == '1':
            reverse = not reverse
        elif query[0] == '2':
            _, F, C = query.split()
            if F == '1':
                if reverse:
                    t.append(C)
                else:
                    t.appendleft(C)
            elif F == '2':
                if reverse:
                    t.appendleft(C)
                else:
                    t.append(C)
    
    result = ''.join(t)
    if reverse:
        result = result[::-1]

    print(result)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [0 for _ in range(N)]
ans = [[0] for _ in range(N)]

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
        
dfs(0,0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
ans = 1
for i in range(n):
    if a.count(0)>0:
        print(0)
        exit()
    ans*= a[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
ans = 1
if a.count(0)>0:
    print(0)
    exit()
for i in range(n):
    l = len(str(ans))
    L = len(str(a[i]))
    if a[i] > 10**18:
        print(-1)
        exit()
    elif l+L > 20:
        print(-1)
        exit()
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))

cnt = 0
for i in range(len(l)):
    for j in range(i+1, len(l)):
        if l[i] + l[j] == abs(i - j):
            cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))

d = [0] * n

cnt = 0
for i in range(len(l)):
    if i + l[i] + 1 < n:
        d[i + l[i]] += 1
    if i - l[i] + 1 > 0:
        cnt += d[i - l[i]]
print(cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

INFTY = 1000000001
cnt = [0]

def merge(left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(INFTY)
    R.append(INFTY)
    i = 0
    j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)

merge_sort(0, N)
print(" ".join(map(str, A)))


### FIXED CODE ###

def counting_sort(MAX):
    C = [0 for _ in range(MAX+1)]

    for i in range(N):
        C[A[i]] += 1

    for i in range(1, MAX+1):
        C[i] = C[i] + C[i-1]

    for i in range(N-1, -1, -1):
        C[A[i]] -= 1
        B[C[A[i]]] = A[i]

N = int(input())
A = list(map(int, input().split()))

MAX = 10001

B = [0 for _ in range(N)]
counting_sort(MAX)
print(" ".join(map(str, B)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))

import itertools

seq = (x for x in range(N))
ptr = list(itertools.combinations(seq,2))
ans = 0
for i in range(len(ptr)):
    if A[ptr[i][0]]+A[ptr[i][1]]==ptr[i][1]-ptr[i][0]:
        ans += 1
        
print(ans)

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
ans = 0

L = [A[x]+x+1 for x in range(N)]
R = [x+1-A[x] for x in range(N)]

cL = collections.Counter(L)
cR = collections.Counter(R)

cRlist = list(cR.keys())

for i in range(len(cRlist)):
    tmp = cRlist[i]
    ans += cR.get(tmp,0) * cL.get(tmp,0)
    
print(ans)
### BUGGY CODE ###

import sys

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

count = 0
saw = []
now = 1

while now not in saw:
    count += 1
    saw.append(now)
    now = a[now - 1]
    if now == 2:
        print(count)
        sys.exit()

print(-1)


### FIXED CODE ###

import sys

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))

count = 0
now = 1

while count < N:
    count += 1
    now = a[now - 1]
    if now == 2:
        print(count)
        sys.exit()

print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

num_cnt = {}
for a_i in a:
    if a_i in num_cnt:
        num_cnt[a_i] += 1
    else:
        num_cnt[a_i] = 1
for a_i in a:
    res = 0;
    for k,v in num_cnt.items():
        x = v-1 if k == a_i else v
        res += x*(x-1)//2
    print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

import collections
cnt = collections.Counter(a)

sum_cnt = 0
for v in cnt.values():
    sum_cnt += v*(v-1)//2

res = []
for value in a:
    res.append(str( sum_cnt - (cnt[value]-1) ))
print('\n'.join(res))
### BUGGY CODE ###

n,m = map(int,input().split())
l = []
for _ in range(m):
    a,b = map(int,input().split())
    l.append([a,b])

# 1から行ける島を列挙する
a = []
for x in l:
    if x[0] == 1:
        a.append(x[1])

# 1から行ける島からNからいける島があったらOK
for y in a:
    for z in l:
        if z[0] == y and z[1] == n:
            print ("POSSIBLE")
            exit ()
print ("IMPOSSIBLE")


### FIXED CODE ###

n,m = map(int,input().split())
l = []
for _ in range(m):
    a,b = map(int,input().split())
    l.append([a,b])

a = []
b = []
for x in l:
    if x[0] == 1:
        a.append(x[1])
    if x[1] == n:
        b.append(x[0])

if set(a) & set(b):
    print ("POSSIBLE")
else:
    print ("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = np.zeros((N+1, W+1), dtype=np.int)
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1,sum_w] = max(dp[i+1,sum_w], dp[i][sum_w-w[i]] + v[i])
        dp[i+1,sum_w] = max(dp[i+1,sum_w], dp[i][sum_w])
print(dp[N][W])

### FIXED CODE ###

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-w[i]] + v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[N][W])
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    sum = 0
    for i in range(0, n-1):
        for j in range(i+1, n):
            sum = (sum + (a[i]*a[j])) % (10**9 + 7)
    print(sum)




### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    cumsum_a = [0] * len(a)
    cumsum_a[0] = a[0]
    for i in range(1, len(a)):
        cumsum_a[i] += cumsum_a[i-1] + a[i]

    sum_val = 0
    num = 10 ** 9 + 7
    for i in range(0, n - 1):
        sum_val += a[i] * (cumsum_a[-1] - cumsum_a[i])
        if sum_val > num:
            sum_val %= num
    print(sum_val)
### BUGGY CODE ###

from collections import deque
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def generate_v2_b(v):
    i, j = divmod(v, w)
    it = [-2, -1, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y

    it = [(-2, 0), (2, 0), (0, -2), (0, 2)]
    for di, dj in it:
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]:
                continue
            dist[v2] = dist[v]
            next_v.append(v2)

        for v2 in generate_v2_b(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)

    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)


### FIXED CODE ###

import heapq
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def dijkstra(init_v):
    next_v = [(0, init_v)]
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


ans = dijkstra(start)[goal]
print(-1 if ans == INF else ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

r = [0] * 60
for i in range(N):
  tmp = format(A[i], '060b')
  #print(tmp)
  for j in range(60):
    r[j] += int(tmp[j])

s = 0
for j in range(60):
  s += r[j] * (N - r[j]) * (2 ** (59-j))
  

print(s % (10**9 + 7))

#print(bin(10**9 + 7))

### FIXED CODE ###

import numpy as np 
N = int(input())
A = np.fromstring(input(), dtype = np.int64, sep = ' ')

res = 0
for bit in range(60):
  c = int((A & 1).sum())
  res += c * (N - c) * (1 << bit)
  A >>= 1

print(res % 1000000007)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**6)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        to[a].append(b)
        to[b].append(a)
    block = [[] for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        block[c].append(d)
        block[d].append(c)

    stack = defaultdict(lambda:[])
    visited = [False] * (N+1)

    def dfs(n, tree= None):
        visited[n] = True
        if tree==None:
            tree = n
        stack[tree].append(n)
        for next in to[n]:
            if not visited[next]:
                dfs(next, tree)
        return None

    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in stack[tree]:
            check_list = to[k] + block[k] + [k]
            for k_ in stack[tree]:
                if not k_ in check_list:
                    candidates[k] += 1

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()
### BUGGY CODE ###

N = int(input())

s = []
for _ in range(N):
    s += [int(input())]

ans = 0
for i in range(2 ** N):
    tmp = 0
    for j in range(N):
        if (i >> j) & 1:
            tmp += s[j]
    if tmp%10 == 0:
        tmp = 0
    ans = max(ans, tmp)

print (ans)

### FIXED CODE ###

#Nの最大値が100なのでbit-DPでは間に合わない

N = int(input())

s = []
total = 0
for _ in range(N):
    a = int(input())
    s += [a]
    total += a

s.sort()
if total % 10 != 0:
    print (total)
    exit()
else:
    for i in range(N):
        if s[i]%10 != 0:
            print (total - s[i])
            exit()
print (0)
### BUGGY CODE ###

import bisect

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
#print("S:", S)
#print("T:", T)

for i in range(Q):
  
  x = X[i]
  answer = 10 ** 12
  
  i1 = bisect.bisect_right(S, x) - 1
  i2 = (i1 + 1) % A
  S1 = S[i1]
  S2 = S[i2]  
  dist1 = abs(x - S1)
  dist2 = abs(x - S2)
  #print("dist1, dist2:", dist1, dist2)
  
  i11 = bisect.bisect_right(T, S1) - 1
  i12 = (i11 + 1) % B
  T11 = T[i11]
  T12 = T[i12]
  dist11 = abs(S1 - T11)
  dist12 = abs(S1 - T12)
  #print("dist11, dist12:", dist11, dist12)
    
  i21 = bisect.bisect_right(T, S2) - 1
  i22 = (i21 + 1) % B
  T21 = T[i21]
  T22 = T[i22]
  dist21 = abs(S2 - T21)
  dist22 = abs(S2 - T22)
  #print("dist21, dist22:", dist21, dist22)
  
  dist = min(dist1 + min(dist11, dist12), dist2 + min(dist21, dist22))
  answer = min(answer, dist)
  
  S, T = T, S
  A, B = B, A

  i1 = bisect.bisect_right(S, x) - 1
  i2 = (i1 + 1) % A
  S1 = S[i1]
  S2 = S[i2]  
  dist1 = abs(x - S1)
  dist2 = abs(x - S2)
  #print("dist1, dist2:", dist1, dist2)
  
  i11 = bisect.bisect_right(T, S1) - 1
  i12 = (i11 + 1) % B
  T11 = T[i11]
  T12 = T[i12]
  dist11 = abs(S1 - T11)
  dist12 = abs(S1 - T12)
  #print("dist11, dist12:", dist11, dist12)
    
  i21 = bisect.bisect_right(T, S2) - 1
  i22 = (i21 + 1) % B
  T21 = T[i21]
  T22 = T[i22]
  dist21 = abs(S2 - T21)
  dist22 = abs(S2 - T22)
  #print("dist21, dist22:", dist21, dist22)
  
  dist = min(dist1 + min(dist11, dist12), dist2 + min(dist21, dist22))
  answer = min(answer, dist)
  
  S, T = T, S
  A, B = B, A

  print(answer)



### FIXED CODE ###

import bisect

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]

answer1 = []
for i in range(Q):
  ii = bisect.bisect_right(S, X[i])
  s1, s2 = ii - 1, ii % A
  d1, d2 = abs(X[i] - S[s1]), abs(X[i] - S[s2])
  
  jj1 = bisect.bisect_right(T, S[s1])
  t11, t12 = jj1 - 1, jj1 % B
  dd11, dd12 = abs(S[s1] - T[t11]), abs(S[s1] - T[t12])

  jj2 = bisect.bisect_right(T, S[s2])
  t21, t22 = jj2 - 1, jj2 % B
  dd21, dd22 = abs(S[s2] - T[t21]), abs(S[s2] - T[t22])
  
  answer1.append(min(d1 + min(dd11, dd12), d2 + min(dd21, dd22)))

S, T = T, S
A, B = B, A
answer2 = []
for i in range(Q):
  ii = bisect.bisect_right(S, X[i])
  s1, s2 = ii - 1, ii % A
  d1, d2 = abs(X[i] - S[s1]), abs(X[i] - S[s2])
  
  jj1 = bisect.bisect_right(T, S[s1])
  t11, t12 = jj1 - 1, jj1 % B
  dd11, dd12 = abs(S[s1] - T[t11]), abs(S[s1] - T[t12])

  jj2 = bisect.bisect_right(T, S[s2])
  t21, t22 = jj2 - 1, jj2 % B
  dd21, dd22 = abs(S[s2] - T[t21]), abs(S[s2] - T[t22])
  
  answer2.append(min(d1 + min(dd11, dd12), d2 + min(dd21, dd22)))

for i in range(Q):
  print(min(answer1[i], answer2[i]))
### BUGGY CODE ###

n=int(input())
ans=1
l=list(map(int,input().split()))
for x in l:
  ans=ans*x
if(ans>1000000000000000000):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n=int(input())
ans=1
l=list(map(int,input().split()))
for x in l:
  if x==0:
    print(0)
    exit()
for x in l:
  ans=ans*x
  if(ans>1000000000000000000):
    break
if(ans>1000000000000000000):
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

import heapq

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
way = [0]
hq = [0]
heapq.heapify(hq)
posi = 0
cycle = 0
while True:
    if a[posi] in way:
        rest = way.index(a[posi])
        cycle -= (rest - 1)
        break
    way.append(a[posi])
    heapq.heappush(hq, a[posi])
    posi = a[posi]
    cycle += 1
# print(way)
# print(cycle)
if k < len(way):
    print(way[k] + 1)
else:
    print(way[(k-rest) % cycle + rest] + 1)

### FIXED CODE ###

import heapq

def binary_search(data, value):
    left = 0            # 探索する範囲の左端を設定
    right = len(data) - 1            # 探索する範囲の右端を設定
    while left <= right:
        mid = (left + right) // 2            # 探索する範囲の中央を計算
        if data[mid] == value:
            # 中央の値と一致した場合は位置を返す
            return mid
        elif data[mid] < value:
            # 中央の値より大きい場合は探索範囲の左を変える
            left = mid + 1
        else:
            # 中央の値より小さい場合は探索範囲の右を変える
            right = mid - 1
    return -1            # 見つからなかった場合

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
way = [0]
hq = [0]
heapq.heapify(hq)
posi = 0
cycle = 0
while True:
    if binary_search(hq, a[posi]) != -1:
        rest = way.index(a[posi])
        cycle -= (rest - 1)
        break
    way.append(a[posi])
    heapq.heappush(hq, a[posi])
    posi = a[posi]
    cycle += 1
# print(way)
# print(cycle)
if k < len(way):
    print(way[k] + 1)
else:
    print(way[(k-rest) % cycle + rest] + 1)
### BUGGY CODE ###

k,s=map(int,input().split())
print([x+y+z for z in range(k+1) for y in range(k+1) for x in range(k+1)].count(s))

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    x=min(s-i,k)-max(0,s-k-i)
    if x>=0:
        ans+=x+1
print(ans)
### BUGGY CODE ###

class Node:
    def __init__(self, i):
        self.num = i
        self.ken = set()
        self.kenken = set()
        self.kenkenpa = set()

N, M = map(int, input().split())
nodes = [Node(i) for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[v].ken.add(nodes[u])

s, t = map(int, input().split())
s -= 1
t -= 1

for i in range(N):
    for pre in nodes[i].ken:
        nodes[i].kenken = nodes[i].kenken | pre.ken

for i in range(N):
    for prepre in nodes[i].kenken:
        nodes[i].kenkenpa = nodes[i].kenkenpa | prepre.ken

num = t
step = 0
check_list = [[num, step]]
check = [False] * N
ok = False
while len(check_list) > 0:
    num, step = check_list.pop(0)
    for pre in nodes[num].kenkenpa:
        if pre.num == s:
            print(step+1)
            ok = True
            break
        if not check[pre.num]:
            check[pre.num] = True
            check_list.append([pre.num, step+1])
    if ok:
        break
if not ok:
    print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
nodes = [[] for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[u].append(v)

s, t = map(int, input().split())
s -= 1
t -= 1

num = s
step = 0
q = [[num, step]]
check = [[False for i in range(N)] for j in range(3)]
ok = False
while len(q) > 0:
    num, step = q.pop(0)
    tmp = step % 3
    if tmp == 0 and num == t:
        print(step//3)
        ok = True
        break
    for next in nodes[num]:
        if not check[tmp][next]:
            check[tmp][next] = True
            q.append([next, step+1])
if not ok:
    print(-1)
### BUGGY CODE ###


def main():
    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    BC = [list(map(int, input().split())) for i in range(M)]

    BC.sort(key=lambda x: x[1], reverse=True)
    A.sort()
    index = 0
    for j in range(M):
        for i in range(BC[j][0]):
            if index >= N:
                break
            if A[index] < BC[j][1]:
                A[index] = BC[j][1]
                index += 1

    print(sum(A))


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    BC = [list(map(int, input().split())) for i in range(M)]

    BC.sort(key=lambda x: x[1], reverse=True)
    A.sort()
    index = 0
    for j in range(M):
        if index >= N:
            break
        elif A[index] > BC[j][1]:
            break
        for i in range(BC[j][0]):
            if index >= N:
                break
            elif A[index] < BC[j][1]:
                A[index] = BC[j][1]
                index += 1

    print(sum(A))


if __name__ == '__main__':
    main()