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

buttons = int(input())
next = []
impossible = []
for i in range(buttons):
    next.append(int(input()))
now_button = 1
ans = 1
while next[now_button - 1] != 2:
    if next[now_button - 1] not in impossible:
        impossible.append(next[now_button - 1])
        now_button = next[now_button - 1]
        ans += 1
    else:
        ans = -1
        break
        
print(ans)
    

### FIXED CODE ###

buttons = int(input())
next_ = []
impossible = []
for i in range(buttons):
    next_.append(int(input()))
now_button = 1
ans = 1
while next_[now_button - 1] != 2:
    if ans <= buttons:
        now_button = next_[now_button - 1]
        ans += 1
        
#    if next_[now_button - 1] not in impossible:
#        impossible.append(next_[now_button - 1])
#        now_button = next_[now_button - 1]
#        ans += 1
    else:
        ans = -1
        break

        
print(ans)
### BUGGY CODE ###

def main():
    A, B, C, D = map(int, input().split())
    mod = 998244353

    dp = [[0]*(D+2) for i in range(C+2)]
    dp[A][B] = 1
    for i in range(A, C+1):
        for j in range(B, D+1):
            ret = dp[i][j]
            if i-A == j-B == 1:
                ret -= (i-1)*(j-1)
            else:
                ret -= dp[i-1][j-1]*(j-1)*(i-1)
            ret %= mod
            dp[i][j] = ret
            dp[i+1][j] += ret * j
            dp[i][j+1] += ret * i

    print(dp[-2][-2])


main()


### FIXED CODE ###

def main():
    A, B, C, D = map(int, input().split())

    c = C - A
    d = D - B
    mod = 998244353
    dp = [[0]*(d+1) for i in range(c+1)]
    dp[0][0] = 1

    for i in range(c+1):

        for j in range(d+1):
            ret = 0
            if i == 0 and j == 0:
                continue
            if i > 0 and j > 0:
                if i == j == 1:
                    ret -= (A+i-1) * (B+j-1)
                else:
                    ret -= dp[i-1][j-1]
                    ret *= (A+i-1)*(B+j-1)
            ret += dp[i-1][j]*(B+j) + dp[i][j-1]*(A+i)

            ret %= mod
            dp[i][j] = ret
    print(dp[c][d])


main()
### BUGGY CODE ###

from collections import Counter
import math
def combinations_count1(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#
N=int(input())
A=list(map(int,input().split()))
#
hoge=Counter(A)
ans1=0
for i in hoge.values():
    if i==1:
        continue
    else:
        ans1+=combinations_count1(i,2)

ans2=[]
for i in A:
    ans2.append(A.count(i)-1)

for k in range(N):
    print(ans1-ans2[k])

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce
def combinations_count2(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

#
N=int(input())
A=list(map(int,input().split()))
#
hoge=Counter(A)
ans=0
for i in hoge.values():
    if i>=2:
        ans += combinations_count2(i, 2)
for i in range(N):
    print(ans-hoge[A[i]]+1)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
a = na()


for p in range(k):
    b = [0]*n
    for i in range(n):
        k = i+a[i]+1
        w = i-a[i]
        if k < n:
            b[k] -= 1
        if 0 <= w:
            b[w] += 1
        else:
            b[0] += 1

    for j in range(1,n):
        b[j] = b[j]+b[j-1]
    a = b

print(*a)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
a = na()
s = n*n


for p in range(k):
    b = [0]*n
    for i in range(n):
        k = i+a[i]+1
        w = i-a[i]
        if k < n:
            b[k] -= 1
        if 0 <= w:
            b[w] += 1
        else:
            b[0] += 1

    for j in range(1,n):
        b[j] = b[j]+b[j-1]
    a = b
    if sum(a) == s:
        break

print(*a)
### BUGGY CODE ###

import numpy as np
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
c = Counter(A)

tmp = np.array(list(c.values()))
l1= tmp*(tmp-1)//2
l2= (tmp-1)*((tmp-1)-1)//2

for a in A:
    r = list(c).index(a)
    sum = np.sum(l1) + l2[r] -l1[r]
    print(int(sum))


### FIXED CODE ###

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

import collections 
c=collections.Counter(A)
sum=0
for i in c:
  sum+=c[i]*(c[i]-1)//2  
for a in A:
  print(sum - c[a]*(c[a]-1)//2 + (c[a]-1)*(c[a]-2)//2)
### BUGGY CODE ###

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

for y in b:
    for x in a:
        if y == x:
            print(a.index(x) + 1, end=' ')

### FIXED CODE ###

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

l = []
for i, x in enumerate(a, 1):
    l.append((x, i))

y = sorted(l)
for z, i in y:
    print(i, end=' ')
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


global memo
memo = []


def solve(li, r, s, p):
    v = []

    def f(li, v):
        if len(li) == 0:
            return 0

        if [li, v] in memo:
            return memo[[li, v]]

        score = 0

        # グーを出す時
        if "r" not in v:
            x = "r"
            if li[0] == "s":
                score = max(score, f(li[1:], ["r"]) + r)
            else:
                score = max(score, f(li[1:], ["r"]))

        # チョキを出す時
        if "s" not in v:
            x = "s"
            if li[0] == "p":
                score = max(score, f(li[1:], ["s"]) + s)
            else:
                score = max(score, f(li[1:], ["s"]))

        # パーを出す時
        if "p" not in v:
            x = "p"
            if li[0] == "r":
                score = max(score, f(li[1:], ["p"]) + p)
            else:
                score = max(score, f(li[1:], ["p"]))

        memo.append([li, score])

        return score
    return f(li, v)


ans = []
for i in range(k):
    ans.append(solve(cir[i], r, s, p))

print(sum(ans))

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(sq):
    # 初手
    x = sq[0]
    if x == "r":
        before, score = "r", p
    elif x == "s":
        before, score = "s", r
    else:
        before, score = "p", s
    cnt = 1

    # 前回と違う手なら問答無用で勝てる、前回と同じ手なら奇数回目に勝てる
    for x in sq[1:]:
        if before != x:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            before = x
            cnt = 1
        elif cnt % 2 == 1:
            cnt += 1
        else:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            cnt += 1
    return score


ans = []
for i in range(k):
    ans.append(solve(cir[i]))

print(sum(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = [0]*(max(A) + 5)
for i in A:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2, max(A) + 5, i):
      ans[j] = 2
print(ans.count(1))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
max_A = A[-1] + 1
ans = [0]*max_A
for i in A:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2, max_A, i):
      ans[j] = 2
print(ans.count(1))
### BUGGY CODE ###

n,m=map(int,input().split())

def c(n,m):
    import math
    if n-m<0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))

def factorize(n):
    fct=[]
    b,e=2,0
    while b*b<=n:
        while n%b==0:
            n=n//b
            e=e+1
        if e>0:
            fct.append((b,e))
        b,e=b+1,0
    if n>1:
        fct.append((n,1))
    return fct

l=factorize(m)
mod=10**9+7
ans=1
for i,j in l:
    ans*=c(j+n-1,j)
    ans=ans%mod

print(ans)

### FIXED CODE ###

n,m=map(int,input().split())

def c(n,m):
    import math
    if n-m<0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))

def factorize(n):
    fct=[]
    b,e=2,0
    while b*b<=n:
        while n%b==0:
            n=n//b
            e=e+1
        if e>0:
            fct.append((b,e))
        b,e=b+1,0
    if n>1:
        fct.append((n,1))
    return fct

l=factorize(m)
mod=10**9+7
ans=1
for i,j in l:
    ans*=c(j+n-1,j)
    ans=ans%mod

print(ans)
### BUGGY CODE ###

N = int(input())
array = list(map(int,input().split()))
pro = [ array[i]*array[i+j] for i in range(N-1) for j in range(1,N-i) ]
print(sum(pro)%(10**9+7))

### FIXED CODE ###

N = int(input())
array = list(map(int,input().split()))
ans = 0
kuso = sum(array)
for i in range(N-1):
  kuso -= array[i]
  ans += array[i]*kuso  
print( ans%(10**9+7) )
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,N = map(int,input().split())
    # AB = [list(map(int,input().split())) for _ in range(N)]
    A = []
    B = []
    for i in range(N):
        temp = list(map(int,input().split()))
        A.append(temp[0])
        B.append(temp[1])

    A = np.array(A)
    B = np.array(B)

    maxA = max(A)
    INF = 10 ** 4 + 1

    dp = [[INF for j in range(H+maxA+1)] for i in range(N)]
    dp[0][0] = 0
    for j in range(1,H+maxA+1):
        time = (j+A[0]-1)//A[0]
        dp[0][j] = B[0] * time

    for i in range(N-1):
        for j in range(H+maxA+1):
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-A[i+1]]+B[i+1])

    res = min(dp[N-1][H:])
    print(res)





main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,N = map(int,input().split())
    # AB = [list(map(int,input().split())) for _ in range(N)]
    A = []
    B = []
    for i in range(N):
        temp = list(map(int,input().split()))
        A.append(temp[0])
        B.append(temp[1])

    # A = np.array(A)
    # B = np.array(B)

    maxA = max(A)
    INF = 10 ** 4 + 1

    dp = [[INF for j in range(H+maxA+1)] for i in range(N)]
    dp[0][0] = 0
    for j in range(1,H+maxA+1):
        time = (j+A[0]-1)//A[0]
        dp[0][j] = B[0] * time

    for i in range(N-1):
        for j in range(H+maxA+1):
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-A[i+1]]+B[i+1])

    res = min(dp[N-1][H:])
    print(res)





main()
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0, N):
    for j in range(i, N):
        for k in range(j, N):
            if i == j or j == k:
                continue
            elif j-i != k-j and S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i + 1, N):
        k = j - i + j
        if k < N:
            if {S[i], S[j], S[k]} == {"R", "G", "B"}:
                ans -= 1
print(ans)
### BUGGY CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = n * [None]
    cost[0] = 0
    for i in range(1, len(h)):
        #cost[i] = min([cost[s] + abs(h[i] - h[s]) for s in range(max(0, i-k), i)])
        cost[i] = min(map(lambda s: cost[s] + abs(h[i] - h[s]), range(max(0, i-k), i)))

    return cost[n-1]


if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)

### FIXED CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = n * [None]
    cost[0] = 0
    for i in range(1, len(h)):
        cost[i] = min([cost[s] + abs(h[i] - h[s]) for s in range(max(0, i-k), i)])
        #cost[i] = min(map(lambda s: cost[s] + abs(h[i] - h[s]), range(max(0, i-k), i)))

    return cost[n-1]


if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
C = [i for i in range(N)]
d = dict(zip(C, A))
B = sorted(A)
B.append(0)
p = B[0]
y = dict()
u = 0
for k in range(N+1):
    q = B[k]
    if p != q:
        y[p] = u
        u=0
    u += 1
    p = q
for j in range(N):
    g = 0
    x = d[j]
    y[x] -= 1
    va = list(y.values())
    for l in va:
        g += l*(l-1)//2
    print(g)
    y[x] += 1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
B.append(0)
p = B[0]
y = dict()
u = 0
for k in range(N+1):
    q = B[k]
    if p != q:
        y[p] = u
        u = 0
    u += 1
    p = q
All = 0
for l in y.values():
    All +=l*(l-1)//2
for j in range(N):
    x = A[j]
    print(All+(y[x]-1)*(y[x]-2)//2-y[x]*(y[x]-1)//2)
### BUGGY CODE ###

s=list(input())
q=int(input())
a=[]
state=0
for i in range(q):
  a.append(input().split())
for i in range(q):
  if a[i][0]=='1':
    state=state^1
  else:
    if (a[i][1]=='1' and state==0) or (a[i][1]=='2' and state==1):
      s.insert(0,a[i][2])
    else:
      s.append(a[i][2])
out=''
if state==1:
  state=-1
else:
  state=1
for x in s[::state]:
  out+=x
print(out)


### FIXED CODE ###

s=input()
q=int(input())

state=0
x,y='',''
for i in range(q):
  a=input().split()
  if a[0]=='1':
    state=state^1
  else:
    if (a[1]=='1' and state==0) or (a[1]=='2' and state==1):
      x=a[2]+x
    else:
      y=y+a[2]
out=x+s+y
if state==0:
  print(out)
else:
  print(out[::-1])
### BUGGY CODE ###

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

num = A[0]
for i in range(1, K):
    num *= A[i]
check = num

for i in range(K, N):
    num //= A[i-K]
    num *= A[i]
    if check < num:
        print('Yes')
    else:
        print('No')
    check = num

### FIXED CODE ###

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

for i in range(K, N):
    if A[i-K] < A[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import functools
import fractions

N = int(input())
A = list(map(int, input().split()))
answer = 0
for i in range(N):
  tmp = A.copy()
  tmp.pop(i)
  gcd = functools.reduce(fractions.gcd, tmp)
  
  if answer < gcd:
    answer = gcd

print(int(answer))


### FIXED CODE ###

import fractions

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

L, R = [0], [0]
for i in range(N):
    L.append(fractions.gcd(L[i], A[i]))
    R.append(fractions.gcd(R[i], A[-i-1]))
L.append(0)
R.append(0)
R = R[::-1]

M = []
for i in range(N):
    M.append(fractions.gcd(L[i], R[i+2]))
print(max(M))
### BUGGY CODE ###

def solve(S):
    dp = [0] * 2019
    ans = 0
    for c in S:
        c = int(c)
        dp2 = [0] * 2019
        dp2[c] = 1
        for i in range(2019):
            if dp[i] == 0: continue
            dp2[(i*10+c)%2019] += dp[i]
        dp = dp2
        ans += dp[0]
    return ans
print(solve(input()))

### FIXED CODE ###

S = input()
r = 1
arr = [0]
for c in S[::-1]:
    arr.append((arr[-1] + int(c) * r) % 2019)
    r *= 10
    r %= 2019
from collections import Counter
ctr = Counter(arr)
ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

n,m,k = map (int,input().split())
def comb(n, r, mod):
  a = 1
  b = 1
  r = min(r, n - r)
  for i in range(r):
    a = a * (n - i) % mod
    b = b * (i + 1) % mod
  return a * pow(b, mod - 2, mod) % mod
mod = 998244353
ans = 0
if k <=  n//2:
    for i in range(k+1):

        ans += (comb (n-1,i,mod) * pow(m-1,n-1-i,mod) * m) % mod
    print(ans % mod)
else:
    for i in range(n-k-1):
        ans += (comb (n-1,n-1- (k+1+i),mod) * pow(m-1,n-1-(k+1+i),mod) * m) % mod
    print((pow(m,n,mod)-ans) % mod)

### FIXED CODE ###

n,m,k = map (int,input().split())
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = 998244353
N = n-1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

mod = 998244353
ans = 0
#if k <=  n//2:
for i in range(k+1):
    ans += (cmb(n-1,i,mod) * pow(m-1,n-1-i,mod) * m) % mod
print(ans % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
col = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
col[a] = 0
low[b]
col[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)  
        col[a] = max(col[a],v)  
        col[b] = max(col[b],v) 
        m = max(m,v)     
print(max(m,dp[A[-1]][A[-1]]+1)+base)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0

for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = max(m,max(dp[a][a],dp[b][b],dp[c][c])+1)
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys


def main():
    D = 60
    n, k = map(int, sys.stdin.buffer.readline().split())

    warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = [0] + warps

    dp = [[0 for j in range(n + 1)] for i in range(D)]
    # print(warps)
    for j in range(1, n + 1):
        dp[0][j] = warps[j]

    for i in range(D - 1):
        for j in range(1, n + 1):
            dp[i + 1][j] = dp[i][dp[i][j]]

    # for dd in dp:
    # print(dd)

    node = 1
    for i in range(D, -1, -1):
        if k >= (1 << i):
            # print(i)
            k -= 1 << i
            node = dp[i][node]

    print(node)


main()



### FIXED CODE ###

#!/usr/bin/env python3

import sys
import numpy as np


def main():
    n, k = map(int, sys.stdin.buffer.readline().split())

    warps = list(map(int, sys.stdin.buffer.readline().split()))
    warps = [0] + warps
    warps = np.array(warps, dtype=int)

    dp = np.zeros((k.bit_length() + 1, n + 1), dtype=int)

    dp[0, :] = warps

    for h in range(1, len(dp)):
        dp[h] = dp[h - 1][dp[h - 1]]

    node = 1
    # for i in reversed(range(k.bit_length())):
    for i in range(k.bit_length(), -1, -1):
        if k >> i & 1:
            node = dp[i][node]

    print(node)


main()
### BUGGY CODE ###

x= int(input())
a = [2]
n = 2
while a[-1] < x:
    n += 1
    if all(n%i for i in a):
        a.append(n)
print(n)

### FIXED CODE ###

def f(n):
    if n==2:return 2
    for i in range(2,[n, 5][n>5]):
        if i**n%n != i:
            return f(n+1)
    return n
print(f(int(input())))
### BUGGY CODE ###

def main():
  n=int(input())
  s=tuple(input())
  r=[i for i, x in enumerate(s) if x == 'R']
  g=[i for i, x in enumerate(s) if x == 'G']
  rg,ans=r+g,0
  b=[i for i in range(n) if not i in rg]
  R,G=len(r),len(g)
  for i in r:
    for j in g:
      ans+=n-R-G +(-1 if (i+j)/2 in b else 0) 
      x,y=((i+j)+abs(i-j)*3)/2,((i+j)-abs(i-j)*3)/2
      ans+=-1 if x in b else 0
      ans+=-1 if y in b else 0
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  R,G,B=s.count('R'),s.count('G'),s.count('B')
  ans=R*G*B
  for i in range(n):
    for j in range(i+1,n):
      if 2*j-i>n-1:
        break
      if s[i]!=s[j] and s[j]!=s[2*j-i] and s[2*j-i]!=s[i]:
        ans-=1
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().strip().split()))[:n]
s=0
for i in range(n):
  for j in range(i+1,n):
    s+=a[i]*a[j]
print(s%(10**9+7))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().strip().split()))[:n]
E=sum(a)**2
s=0
s=sum(i*i for i in a)
print(((E-s)//2)%(10**9+7))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 1
for i in a:
  res *= i
if res > 10 ** 18:
  res = -1
print(res)

### FIXED CODE ###

def f(a):
	res = 1
	for i in range(n):
		res *= int(a[i])
		if res > 10 ** 18:
			if zer(i):
				return 0
			else:
				return -1
	return res

def zer(i):
	for j in range(i, n):
		if a[j] == "0":
			return True
	return False
n = int(input())
a = input().split()

print(f(a))
### BUGGY CODE ###

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

ans = 1
can = 1
zero = 0

if 0 in a:
    zero = 1
    ans = 0

if(zero==0):
    for i in range(N):
        ans = ans * a[i]
        if(ans>1000000000000000000):
            can = 0

if(can==1):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

ans = 1
can = 1
zero = 0

if 0 in a:
    zero = 1
    ans = 0

if(zero==0):
    for i in range(N):
        ans = ans * a[i]
        if(ans>1000000000000000000):
            can = 0
            break

if(can==1):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

w, x = input().split(" ")
a = int(w)
b = int(x)

def compute_lcm(x, y):
   if x > y:
       greater = x
   else:
       greater = y
   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1
   return lcm

print(compute_lcm(a, b))

### FIXED CODE ###

w, x = input().split(" ")
a = int(w)
b = int(x)

def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm

print(compute_lcm(a, b))
### BUGGY CODE ###

import itertools
N, M = map(int, input().split())
A = list(map(int, input().split()))
l = []
for i in range(M):
  b, c = map(int, input().split())
  l.append([c]*b)
  
m = list(itertools.chain.from_iterable(l))
A.sort()
m.sort(reverse=True)

j = 0
while (j < len(m)) and (A[j] < m[j]):
  A[j] = m[j]
  j += 1
  
print(sum(A))

### FIXED CODE ###

import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    change = [[int(i) for i in input().split()] for _ in range(M)]
    change.sort(key = itemgetter(1), reverse = True)

    ai = 0
    for i in range(M):
        cb, c = change[i]
        if ai >= N or c < A[ai]: break
        for _ in range(cb):
            if ai >= N: break
            if A[ai] <= c:
                A[ai] = c
                ai += 1
            else: break
    print(sum(A))
    return 0

if __name__ == "__main__":
    solve()