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

from functools import lru_cache

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


MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)

@lru_cache(maxsize=None)
def nCr(n, r, p=MOD):
    # Modulo binomial coefficients
    num = 1
    den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return num * modInverse(den, p) % p


if N - 1 < K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 <= N
    tot = 0
    for numEmpty in range(K + 1):
        numNonEmpty = N - numEmpty
        stars = numEmpty  # Everyone moving into an occupied room
        bars = numNonEmpty - 1
        tot += nCr(stars + bars, bars) * nCr(N, numEmpty)
    print(tot % MOD)


### FIXED CODE ###

from functools import lru_cache


CHECK = False

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

MOD = 10 ** 9 + 7


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


if N - 1 <= K or CHECK:
    fact = [1]
    for i in range(1, 2 * N + 1):
        fact.append((fact[-1] * i) % MOD)

    def nCr(n, r, p=MOD):
        # Modulo binomial coefficients
        return (fact[n] * modInverse(fact[r], p) * modInverse(fact[n - r], p)) % p


if N - 1 <= K:
    # Any combo is achievable so this is stars and bars
    # N people into N rooms, which means N - 1 dividers
    stars = N
    bars = N - 1
    print(nCr(stars + bars, bars))
else:
    # Group by number of empty rooms
    # With K moves there can only be at most K empty rooms
    # Max of N - 1 empty rooms in general
    assert K + 1 < N
    tot = 0
    comb1 = 1
    comb2 = 1
    for numEmpty in range(K + 1):
        way3 = comb1 * comb2
        if CHECK:
            numNonEmpty = N - numEmpty
            stars = numEmpty  # Everyone moving into an occupied room
            bars = numNonEmpty - 1  # Number of dividers
            way1 = nCr(stars + bars, bars) * nCr(N, numEmpty)

            way2 = nCr(N, numEmpty) * nCr(N - 1, numEmpty)

            assert way1 % MOD == way2 % MOD == way3 % MOD
        tot += way3

        j = numEmpty + 1
        invJ = modInverse(j, MOD)
        comb1 = (N + 1 - j) * comb1 * invJ % MOD
        comb2 = (N - j) * comb2 * invJ % MOD
    print(tot % MOD)
### BUGGY CODE ###

s = input()
Q = int(input())

for _ in range(Q):
    q = input().split()

    if q[0] == "1":
        s = s[::-1]
    elif q[0]=="2":
        tmp = q[2]
        if q[1] == "1":
            tmp += s
            s = tmp
        elif q[1] =="2":
            s += tmp
print(s)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    s = input()
    s = s[0:len(s)-1]
    Q = int(input())
    head = []
    tail = []

    flg = 0 # 0:sonomama 1:gyakuten
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            if flg == 0:
                flg = 1
            else:
                flg = 0
        elif q[0]=="2":
            index,tmp = q[1],q[2]
            if (index == "1" and flg ==0) or (index == "2" and flg ==1):
                head.append(tmp)
            elif (index == "2" and flg == 0) or (index == "1" and flg == 1):
                tail.append(tmp)

    s1 = "".join(head)
    s1 = s1[::-1]
    s2 = "".join(tail)
    ans = s1 + s + s2
    if flg == 1:
        ans = ans[::-1]

    print(ans)

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

import sys
input = sys.stdin.readline

INF = 10 ** 8 + 1
n, m = map(int, input().split())
state_num = 1 << n
key = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bt = 0
    for e in c:
        bt |= 1 << (e - 1)
    key.append((bt, a))

dp = [INF for _ in range(state_num)]
dp[0] = 0

for i in range(state_num):
    for j in range(m):
        ks, kc = key[j]
        state = i | ks
        cost = dp[i] + kc
        dp[state] = min(dp[state], cost)

ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():

    INF = 10 ** 7
    n, m = map(int, input().split())
    state_num = 1 << n
    key = []
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bt = 0
        for e in c:
            bt |= 1 << (e - 1)
        key.append((bt, a))

    dp = [INF for _ in range(state_num)]
    dp[0] = 0

    for i in range(state_num):
        for j in range(m):
            ks, kc = key[j]
            state = i | ks
            cost = dp[i] + kc
            dp[state] = min(dp[state], cost)

    ans = dp[-1]
    if ans == INF:
        ans = -1
    print(ans)


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

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

dp = [[[0] * (50 * (n + 10)) for _ in range(n + 10)] for _ in range(n + 10)]
dp[0][0][0] = 1

for i in range(n):
    for use in range(n):
        for total in range(n * a):
            dp[i + 1][use][total] += dp[i][use][total]
            dp[i + 1][use + 1][total + x[i]] += dp[i][use][total]

ans = 0
for i in range(1, n + 1):
    ans += dp[n][i][a * i]

print(ans)


### FIXED CODE ###

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

dp = [[[0] * (50 * (n + 10)) for _ in range(n + 10)] for _ in range(n + 10)]
dp[0][0][0] = 1

for i in range(n):
    for use in range(n):
        for total in range(n * a):
            if dp[i][use][total]:
                dp[i + 1][use][total] += dp[i][use][total]
                dp[i + 1][use + 1][total + x[i]] += dp[i][use][total]

ans = 0
for i in range(1, n + 1):
    ans += dp[n][i][a * i]

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

from itertools import product
n = int(input())
s = input()
ans = 0
for p in product([0,1], repeat=2*n):
    left = right = ""
    for j in range(2*n):
        if p[j]:
            left += s[j]
        else:
            right += s[j]
    right = right[-1::-1]
    if left == right:
        ans += 1
print(ans)


### FIXED CODE ###

from itertools import product
from collections import defaultdict
n = int(input())
s = input()
sa, sb = s[:n], s[n:][::-1]
a, b, ans = defaultdict(int), defaultdict(int), 0
for p in product(range(2), repeat=n):
    word_a_1, word_b_1, word_a_2, word_b_2 = "", "", "", ""
    for j in range(n):
        if p[j]:
            word_a_1 += sa[j]
            word_b_1 += sb[j]
        else:
            word_a_2 += sa[j]
            word_b_2 += sb[j]
    a[(word_a_1, word_a_2)] += 1
    b[(word_b_1, word_b_2)] += 1
while a:
    key, value = a.popitem()
    ans += value * b[key]
print(ans)
### BUGGY CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))

cnt_list = [int_list.count(i) for i in range(1, N+1)]
ret_list = []

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] < 2:
        continue
    else:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2

# for i in range(N):
#     if cnt_list[i] < 1:
#         tmp_ret = 0
#     else:
#         tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
#     ret_list.append(tmp_ret)

ret_list = [0 if cnt_list[i] < 1 else tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2 for i in range(N)]

for i in int_list:
    print(ret_list[i-1])

### FIXED CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [0] * N

for i in int_list:
    cnt_list[i-1] += 1

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2


for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])
### BUGGY CODE ###

N,M,P = map(int,input().split())

edge_dic = {}

for _ in range(M):
    A,B,C = map(int,input().split())
    if not A - 1 in edge_dic:
        edge_dic[A-1] = [[B-1,C-P]]
    else:
        edge_dic[A-1].append([B-1,C-P])

# print(edge_dic)

INF = 10 ** 10

ans_array = [-INF] * N

ans_array[0] = 0
last_ans_change = -1

for i in range(N*3):
    change_flag = 0
    for key, value in edge_dic.items():
        for v in value:
            goal, cost = v
            if ans_array[goal] < ans_array[key] + cost:
                ans_array[goal] = ans_array[key] + cost
                change_flag = 1
                if goal == N - 1:
                    last_ans_change = i
    if change_flag == 0:
        break

if last_ans_change >= N * 2:
    ans = -1
else:
    ans = max(0,ans_array[N-1])

print(ans)

### FIXED CODE ###

N,M,P = map(int,input().split())

edge_dic = {}

for _ in range(M):
    A,B,C = map(int,input().split())
    if not A - 1 in edge_dic:
        edge_dic[A-1] = [[B-1,C-P]]
    else:
        edge_dic[A-1].append([B-1,C-P])

# print(edge_dic)

INF = 10 ** 10

ans_array = [-INF] * N
can_visit = [0] * N
ans_array[0] = 0
can_visit[0] = 1 
last_ans_change = -1

for i in range(N*2):
    change_flag = 0
    for key, value in edge_dic.items():
        if can_visit[key] == 0:
            continue
        for v in value:
            goal, cost = v
            if ans_array[goal] < ans_array[key] + cost:
                ans_array[goal] = ans_array[key] + cost
                if i >= N:
                    ans_array[goal] = INF
                can_visit[goal] = 1
                change_flag = 1
                if goal == N - 1:
                    last_ans_change = i
                    if i >= N:
                        print(-1)
                        exit()
    if change_flag == 0:
        break


ans = max(0,ans_array[N-1])

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

S = list(input())
Q = int(input())

reverse = True
for _ in range(Q):
  q = list(input())
  if q[0] == "1":
    if reverse: reverse = False
    else: reverse = True
  else:
    if reverse:
      if q[2] == "1": S.insert(0, q[4])
      else: S.append(q[4])
    else:
      if q[2] == "1": S.append(q[4])
      else: S.insert(0, q[4])

print("".join(S) if reverse else "".join(S[::-1])) 

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
q = [list(input().split()) for _ in range(Q)]

ok = True #Falseで反転させる
for i in range(Q):
    l = q[i]
    if l[0] == "1":
        if ok: ok = False
        else: ok = True
    else:
        if ok:
            if l[1] == "1": S.appendleft(l[2])
            else: S.append(l[2])
        else:
            if l[1] == "1": S.append(l[2])
            else: S.appendleft(l[2])
if not ok:
    S = list(S)[::-1]
print("".join(list(S)))
### BUGGY CODE ###

K,S = map(int,input().split())

result = 0

for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                result+=1
print(result)

### FIXED CODE ###

K,S = map(int,input().split())

result = 0

for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
                result+=1
print(result)
### BUGGY CODE ###

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

A = sorted([a - i for a, i in enumerate(A)])

result = 0
while len(A) > 1:
  result += A[-1] - A[0]
  A = A[1:-1]

print(result)

### FIXED CODE ###

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

A = sorted([a - i for a, i in enumerate(A)])

print(sum(abs(x-y) for x,y in zip(A, A[::-1]))//2)
### BUGGY CODE ###

N, M = map(int, input().split())
L = list(list(map(int,input().split())) for i in range(M))
A = list(range(L[0][0],L[0][1]+1))
for i in range(1,M):
    A.extend(list(range(L[i][0],L[i][1]+1)))
count = 0
for i in range(1,N+1):
    if A.count(i) == M:
        count +=1
print(count)

### FIXED CODE ###

N, M = map(int, input().split())
L = list(list(map(int,input().split())) for i in range(M))
l = 1
r = N
for i in range(M):
    l = max(l,L[i][0])
    r = min(r,L[i][1])
print(max(r-l+1,0))
### BUGGY CODE ###

#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
cnt = 0
for i in range(n):
    if h[i] <= 0:
        continue
        
    idx = bisect_right(x, x[i] + 2 * d)
    cur_cnt = -(-h[i] // a)
    for j in range(i, idx):
        h[j] -= cur_cnt * a
    
    cnt += cur_cnt
    
print(cnt)

### FIXED CODE ###

#153_F
from bisect import bisect_right
n, d, a = map(int, input().split())
mons = sorted([tuple(map(int, input().split())) for _ in range(n)])
x = [mons[i][0] for i in range(n)]
h = [mons[i][1] for i in range(n)]
damage = [0 for _ in range(n+1)]
cnt = 0
for i in range(n):
    if i > 0:
        damage[i] += damage[i-1]
        if h[i] <= damage[i]:
            continue
    
    cur_cnt = -(-(h[i]-damage[i]) // a)
    cnt += cur_cnt
    damage[i] += cur_cnt * a
    idx = bisect_right(x, x[i] + 2 * d)
    damage[idx] -= cur_cnt * a
    
print(cnt)
### BUGGY CODE ###

k = int(input())
s = input()

n = len(s)
mod = 10**9+7


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


num = 0
for i in range(0, k+1):
    num = num+comb(i+n-1, n-1, mod)*pow(25, i,
                                        mod) % mod * pow(26, k-i, mod) % mod
print(num)


### FIXED CODE ###

k = int(input())
s = input()

n = len(s)
mod = 10**9+7


def framod(n, mod, a=1):
    for i in range(1, n+1):
        a = a * i % mod
    return a


def power(n, r, mod):
    if r == 0:
        return 1
    if r % 2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r % 2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod):
    a = framod(n, mod)
    b = framod(k, mod)
    c = framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod


com = [1]*(k+1)
for i in range(k):
    com[i+1] = com[i]*(n+i)*pow(i+1, mod-2, mod) % mod

a25 = [1]*(k+1)
for i in range(k):
    a25[i+1] = a25[i]*25 % mod
a26 = [1]*(k+1)
for i in range(k):
    a26[i+1] = a26[i]*26 % mod
num = 0
for i in range(0, k+1):
    num = (num+com[i]*a25[i] % mod * a26[k-i]) % mod
print(num)
### BUGGY CODE ###

n = input()
words_org = []
for i in range(int(n)):
  words_org.append(input())


countDic = { k: words_org.count(k) for k in set(words_org) }
ranking = sorted([item for item in countDic.items()], key = lambda x:x[1], reverse=True)
order = 0
top = ranking[0][1]
candidates = []
while ranking[order][1] == top:
  candidates.append(ranking[order][0])
  order += 1
  if order > len(ranking)-1:
    break
for word in sorted(candidates):
  print(word)

### FIXED CODE ###

N = input()
dic = {}
max = 0
for i in range(int(N)):
  word = input()
  if word not in dic.keys():
    
    if max == 0:
      max += 1
    dic[word] = 1
    
  else:
    
    if max == dic[word]:
      max += 1
    dic[word] += 1

candidates = sorted([word for word in dic.keys() if dic[word] == max])
for word in candidates:
  print(word)
### BUGGY CODE ###

N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n+1)]
    for i in range(n//2):
        p=(i+1)**2
        if p>n:
            for j in range(i**2,n+1):
                A[j]=i
            break
        else:
            for j in range(i**2,p):
                A[j]=i
    return A
A=sq(N)[0:N+1]
for n in range(1,N+1):
    c=0
    for x in range(1,A[n]):
        p=n-x**2
        if p<0:
            break
        else:
            for y in range(1,A[p]):
                q=n-x**2-y**2
                if q<0:
                    break
                else:
                    for z in range(1,A[n-x**2-y**2]):
                        if n==x**2+y**2+z**2+x*y+y*z+z*x:
                            c=c+1
    print(c)

### FIXED CODE ###

N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n+1)]
    for i in range(n//2):
        p=(i+1)**2
        if p>n:
            for j in range(i**2,n+1):
                A[j]=i
            break
        else:
            for j in range(i**2,p):
                A[j]=i
    return A
A=sq(N)
a=A[N]
L=[0 for j in range(N+1)]
for x in range(1,a+1):
    for y in range(1,a+1):
        for z in range(1,a+1):
            p=x**2+y**2+z**2+x*y+y*z+z*x
            if p<=N:
                L[p]=L[p]+1
            else:
                break
for i in range(1,N+1):
    print(L[i])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    b=a[i]*sum(a[i+1:n])
    ans=ans+b
d=ans%(1000000007)
print(d)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
c=sum(a)
for i in range(n):
    c=c-a[i]
    b=(a[i]*c)
    ans=ans+b
d=ans%(1000000007)
print(d)
### BUGGY CODE ###

n,w=map(int,input().split())
li=[[int(i) for i in input().split()] for j in range(n)]

dp = [[0 for i in range(w+1)] for j in range(n+1)]

ans = 0
for i in range(n):
    for j in range(1,w+1):
        if li[i][0] <= j:
            dp[i+1][j]=max(dp[i][j], dp[i][j-li[i][0]]+li[i][1])
        else:
            dp[i+1][j]=dp[i][j]
        ans = max(ans,dp[i+1][j])
print(ans)

### FIXED CODE ###

n,w=map(int,input().split())
#wv=[[int(i) for i in input().split()] for j in range(n)]
dp=[0]*(w+1)

for i in range(n):
    new_dp=[0]*(w+1)
    ww,v=map(int,input().split())
    for j in range(w+1):
        if j<ww:
            new_dp[j]=dp[j]
        else:
            new_dp[j]=max(dp[j],dp[j-ww]+v)
    dp=new_dp
print(dp[-1])
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]

    bh_destroy = bomb_most_h[1]
    bw_destroy = bomb_most_w[1]
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    ans = bh_destroy+bw_destroy
    
    
    for bh in candidate_h:
        for bw in candidate_w:   
            if not([bh,bw] in BOMB_HW):
                print(ans)
                sys.exit()
    print(ans-1)
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, W, M = NMI()
    
    BOMB_HW = [NLI() for _ in range(M)]
    
    bomb_h,bomb_w = zip(*BOMB_HW)
    
    dd = defaultdict(bool)
    for m in range(M):
        dd[str(bomb_h[m]) + "-" + str(bomb_w[m])] = True
    
    c_h = collections.Counter(bomb_h)
    c_w = collections.Counter(bomb_w)
    
    bomb_most_h = c_h.most_common()[0]
    bomb_most_w = c_w.most_common()[0]

    bh_destroy = bomb_most_h[1]
    bw_destroy = bomb_most_w[1]
 
    candidate_h = [i[0] for i in c_h.items() if i[1] == bh_destroy]
    candidate_w = [i[0] for i in c_w.items() if i[1] == bw_destroy]

    ans = bh_destroy+bw_destroy
    

    for bh in candidate_h:
        for bw in candidate_w:   
            if not(dd[str(bh) + "-" + str(bw)]):
                print(ans)
                sys.exit()
    print(ans-1)
    


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

n, q = map(int, input().split())
s = input()

for i in range(q):
    l, r = map(int, input().split())
    s_i = s[l-1:r]
    print(s_i.count("AC"))


### FIXED CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
w = np.zeros(n, dtype=int)

a = 0
for i in range(n):
    if s[i] == "A":
        if a == 0:
            a += 1
    elif s[i] == "C":
        if a:
            w[i-1] = 1
            a -= 1
    else:
        if a:
            a -= 1

ans = np.append(np.zeros(1, dtype=int), np.cumsum(w))
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])
### BUGGY CODE ###

N = int(input())

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

m = 1

for a in A:
    m = m * a

if m > 1000000000000000000:
    print(-1)
    exit(0)

print(m)

### FIXED CODE ###

N = int(input())

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

m = 1

A.sort()
if A[0] == 0:
    print(0)
    exit(0)


for a in A:
    m = m * a

    if m > 1000000000000000000:
        print(-1)
        exit(0)



print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
li_A = list(map(int, input().split()))
for i in range(M):
    li_A.sort()
    B, C = map(int, input().split())
    for j in range(B):
        if li_A[j] < C:
            li_A[j] = C
print(sum(li_A))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
heap = list(map(int, input().split()))
heapify(heap)

BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append([B, C])
BC.sort(key=lambda x: -x[1])

for B, C in BC:
    for _ in range(B):
        tmp = heappop(heap)
        if tmp < C:
            heappush(heap, C)
        else:
            heappush(heap, tmp)
            break
print(sum(heap))
### BUGGY CODE ###

n, m = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
cnt = [0]*n
for i in range(m):
    for j in range(lr[i][0]-1, lr[i][1]):
        cnt[j] += 1
ans = sum(i==m for i in cnt)
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
left = 0
right = n+1
for i in range(m):
    l, r = map(int, input().split())
    left = max(left, l)
    right = min(right, r)
ans = 0
for i in range(left-1, right):
    ans += 1
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x + y + z == S:
                count+=1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S-(x+y) <= K:
            count+=1
print(count)
### BUGGY CODE ###

import numpy as np
R,G,B,N = list(map(int, input().split()))

s = 0
for nr in np.arange(N//R + 1):
    Nr = N - nr * R
    for ng in np.arange(Nr//G + 1):
        Nrg = Nr - ng * G
        if Nrg%B == 0:
            s += 1
print(s)

### FIXED CODE ###

import numpy as np
from collections import Counter
R,G,B,N = list(map(int, input().split()))
a = [R, G, B]
a.sort()
a = a[::-1]
R, G, B = a

s = 0
r_cand = np.arange(0, N + 1, R)[:, None]
g_cand = np.arange(0, N + 1, G)[None, :]
rest = N - r_cand - g_cand
rest = rest[rest >= 0]
c = Counter(rest)

s = 0
for k in c.keys():
    s += (k%B == 0) * c[k]

print(s)