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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(301,301,301)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = 1
            p = 0
            if i1>0:
                ans += i1/n * sub[i1-1][i2][i3]
                p += i1/n
            if i2>0:
                ans += i2/n * sub[i1+1][i2-1][i3]
                p += i2/n
            if i3>0:
                ans += i3/n * sub[i1][i2+1][i3-1]
                p += i3/n
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

def main():
    r, c, k = map(int, input().split())
    d = dict()
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[(t1-1, t2-1)] = t3
    dp = [[[0]*4 for _ in [0]*c] for _ in [0]*r]
    if (0, 0) in d:
        dp[0][0][1] = d[(0, 0)]
    for x in range(r):
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        if (x, y+1) in d:
                            dp[x][y+1][z+1] = max(dp[x][y+1]
                                                  [z+1], dp[x][y][z]+d[(x, y+1)])
                    dp[x][y+1][z] = max(dp[x][y+1][z], dp[x][y][z])
            if x != r-1:
                if (x+1, y) in d:
                    dp[x+1][y][1] = max(dp[x+1][y][1],
                                        max(dp[x][y])+d[(x+1, y)])
                dp[x+1][y][0] = max(dp[x+1][y][0], max(dp[x][y]))
    print(max(dp[r-1][c-1]))


main()

### FIXED CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()
### BUGGY CODE ###

H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
ans = 0
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[i][x] = cou
            Grid1[i][j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            Grid1[i][x] = cou
ws = [0]*H
    
for i in range(W):
    cou = 0
    l = 0
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                ws[x] = cou
            ws[j] = 0
            l = j+1
            cou = 0
        for x in range(l,j+1):
            ws[x] = cou
    for j in range(H):
        ans =max(Grid1[j][i] +ws[j], ans)

print(ans-1)


### FIXED CODE ###

H,W = map(int,input().split())
S = list(input() for i in range(H))
Grid1 = [[0]*W for i in range(H)]
for i in range(H):
    cou = 0
    l = 0
    for j in range(W):
        if S[i][j] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[i][x] = cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[i][x] = cou    
for i in range(W):
    cou = 0
    l = 0
    for j in range(H):
        #print(i,j,S[i][j])
        if S[j][i] == ".":
            cou += 1
        else:
            for x in range(l,j):
                Grid1[x][i] += cou
            l = j+1
            cou = 0
    for x in range(l,j+1):
        Grid1[x][i] += cou

print(max(max(Grid1[i]) for i in range(H))-1)
### BUGGY CODE ###

h, w, k = map(int, input().split())
ar = [list(map(int, input())) for _ in range(h)]

ans = None
for i in range(2**(h - 1)):
    t = 0
    to_add = [0]
    for a in range(h - 1):
        if i & (2**a):
            t += 1
        to_add.append(t)
    n_h = t
    n_w = 0
    zz = [0 for _ in range(n_h + 1)]
    cnts = zz.copy()
    for x in range(w):
        is_over = False
        for y in range(h):
            z = to_add[y]
            cnts[z] += ar[y][x]
            if cnts[z] > k:
                is_over = True
                break
        if is_over:
            n_w += 1
            if ans is not None and ans <= n_h + n_w:
                break
            cnts = [0 for _ in range(n_h + 1)]
            cnts = zz.copy()
            for y in range(h):
                cnts[to_add[y]] += ar[y][x]
    if ans is None or ans > n_h + n_w:
        ans = n_h + n_w
print(ans)


### FIXED CODE ###

h, w, k = map(int, input().split())
ar = [list(map(int, input())) for _ in range(h)]

ans = None
for i in range(2**(h - 1)):
    t = 0
    to_add = [0]
    for a in range(h - 1):
        if i & (2**a):
            t += 1
        to_add.append(t)
    n_h = t
    n_w = 0
    zz = [0 for _ in range(n_h + 1)]
    cnts = zz.copy()
    is_new = True
    is_fail = False
    for x in range(w):
        is_over = False
        for y in range(h):
            z = to_add[y]
            cnts[z] += ar[y][x]
            if cnts[z] > k:
                is_over = True
                break
        if is_over:
            n_w += 1
            if ans is not None and ans <= n_h + n_w:
                break
            cnts = zz.copy()
            for y in range(h):
                z = to_add[y]
                cnts[z] += ar[y][x]
                if cnts[z] > k:
                    is_fail = True
                    break
            if is_fail:
                break
    if not is_fail and (ans is None or ans > n_h + n_w):
        ans = n_h + n_w
print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
MOD = 998244353

dp = [[0] * (N + 1) for _ in range(N)] 
dp[0][0] = M

for i in range(N - 1):
  for j in range(N):
    dp[i+1][j] += dp[i][j] * (M-1)
    dp[i+1][j+1] = dp[i][j] * 1
print(sum(dp[-1][:K+1]) % MOD)

### FIXED CODE ###

N, M, K = map(int, input().split())
MOD = 998244353

ans = 0

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % MOD
        self.ifact[n] = pow(self.fact[n], MOD-2, MOD)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % MOD
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %MOD
        return comb
comb = combination(N)

  
for k in range(K+1):
  # M x (N-1)Ck x (M-1) ^ (N - 1 - k)
  ans += (comb.comb(N-1, k) * pow(M-1, N-1-k, MOD)) % MOD
  
print(ans * M % MOD)
### BUGGY CODE ###

N, K = map(int, input().strip().split())
count = set()
for a in range(K, N+1, K):
    for b in range(K, N + 1, K):
        for c in range(K, N + 1, K):
            count.add((a, b, c))

if K % 2 == 1:
    print(len(count))
else:
    start = K // 2
    for a in range(start, N + 1, K):
        for b in range(start, N + 1, K):
            for c in range(start, N + 1, K):
                count.add((a, b, c))
    print(len(count))

### FIXED CODE ###

N, K = map(int, input().strip().split())
result = 0
num = N // K
result += num
if num == 2:
    result += num * (num - 1) * 3
elif num > 2:
    result += num * (num - 1) * 3
    result += num * (num - 1) * (num - 2)


if K % 2 == 1:
    print(result)
else:
    start = K // 2
    num = (N - start) // K + 1
    result += num
    if num == 2:
        result += num * (num - 1) * 3
    elif num > 2:
        result += num * (num - 1) * 3
        result += num * (num - 1) * (num - 2)
    print(result)
### BUGGY CODE ###

s = input()
q_number = int(input())
reverse_flag = 1
for i in range(q_number):
  temp = input().split()
  if temp[0] == "1": 
    reverse_flag = reverse_flag * -1
  else:
    headstails = int(temp[1])*reverse_flag 
    if headstails == 1 or headstails == -2:
      s = temp[2] + s
    else:
      s = s + temp[2]      
      
if reverse_flag == -1:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q_number = int(input())
reverse_flag = 1
head = ""
tail = ""
for i in range(q_number):
  temp = input().split()
  if temp[0] == "1": 
    reverse_flag = reverse_flag * -1
  else:
    headstails = int(temp[1])*reverse_flag 
    if headstails == 1 or headstails == -2:
      head = temp[2] + head
    else:
      tail = tail + temp[2]
      
if reverse_flag == 1:
  print(head+s+tail)
else:
  print(tail[::-1]+s[::-1]+head[::-1])
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(k):
  if a >= 1:
    a -= 1
  elif b >= 1:
    b -= 1
print("{} {}".format(a, b))

### FIXED CODE ###

a, b, k = map(int, input().split())

if k != 0:
    diva = a / k
    if diva >= 1:
        a -= k
    else:
        k -= a
        a = 0
        b -= k
        if b < 0:
            b = 0
print("{} {}".format(a, b))
### BUGGY CODE ###

from collections import deque
from bisect import bisect_left
n=int(input())
a=sorted(list(map(int,input().split())))

sus=deque([sum(a)])
q=int(input())
for i in range(q):
  count=0
  b,c=map(int,input().split())
  idx=bisect_left(a,b)
  while True:
    if idx>=n:break
    if a[idx]==b:
      a[idx]=c
      count+=1
      idx+=1
    else:
      break
  a=sorted(a)
  sus.append(sus[-1]+(c-b)*count)
  print(sus[-1])

### FIXED CODE ###

n=int(input())
a=[0]*(10**5)
A=list(map(int,input().split()))
su=0
for i in range(n):
  su+=A[i]
  a[A[i]-1]+=1
q=int(input())
sus=[su]
for i in range(q):
  
  b,c=map(lambda x:int(x)-1,input().split())
  sus.append(sus[-1]+(c-b)*a[b])
  a[c]+=a[b]
  a[b]-=a[b]
  print(sus[-1])
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    ret = 0
    for i in range(n):
        if A[i]+m < A[n-p]:
            continue
        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            ret = n-i
            break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    left, right = -1, n

    while left+1 < right:
        i = (left+right)//2

        if A[i]+m < A[n-p]:
            left = i
            continue

        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            right = i
        else:
            left = i

    return str(n-right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
x,k,d=map(int,input().split())
if x<0:
  x+=d*k
  m=abs(x)
  for i in range(k):
    x-=d*2
    if abs(x)<m:
      m=abs(x)
    else:
      break
  print(m)
else:
  x-=d*k
  m=abs(x)
  for i in range(k):
    x+=d*2
    if abs(x)<m:
      m=abs(x)
    else:
      break
  print(m)

### FIXED CODE ###

# -*- coding: utf-8 -*-
x,k,d=map(int,input().split())
m=abs(x)
n=m//d
j=k-n
if j>0:
  if x<0:
    if j%2==0:
      x+=d*n
    else:
      x+=d*(n+1)
  else:
    if j%2==0:
      x-=d*n
    else:
      x-=d*(n+1)
else:
  if x<0:
    x+=d*k
  else:
    x-=d*k
print(abs(x))
### BUGGY CODE ###

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

result=1

if 0 in A:
    result=0
else:
    for i in A:
        result = result*i
    if result > 10**18:
        result=-1
print(result)

### FIXED CODE ###

import sys
n = input()
list_num =list(map(int,input().split()))
output = 1
if 0 in list_num:
    print(0)
    sys.exit()
for i in list_num:
    output = output * i
    if output > 10 ** 18:
        print(-1)
        sys.exit()
print(output)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(500000)


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

e_list = [[] for i in range(N)]

for i in range(M):
    x,y = list(map(int,input().split()))
    x,y = x-1,y-1
    e_list[x].append(y)

from functools import lru_cache

@lru_cache(maxsize=N)
def DFS(v):
    if len(e_list[v])==0:
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(500000)


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

e_list = [[] for i in range(N)]

for i in range(M):
    x,y = list(map(int,input().split()))
    x,y = x-1,y-1
    e_list[x].append(y)

memo = [-1]*N

def DFS(v):
    if memo[v]!=-1:
        return memo[v]
    if len(e_list[v])==0:
        memo[v] = 0
        return 0
    res = 0
    for v1 in e_list[v]:
        res1 = DFS(v1)
        if res<res1+1:
            res = res1+1
    memo[v] = res
    return res

ans = 0
for i in range(N):
    res = DFS(i)
    if res>ans:
        ans = res
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
A=[a for a in A if a<K]
from collections import defaultdict
N=len(A)
bord=-1
can={0}
now=0
for i in range(N):
    flag=False
    canc=can.copy()
    for x in canc:
        if K-A[i]<=x<K:
            flag=True
        if x+A[i]<K:
            can|={x+A[i]}
    if flag:
        bord=i
print(N-bord-1)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
S=0
ans=0
for a in A:
    if S+a<K:
        S+=a
        ans+=1
    else:ans=0
print(ans)
### BUGGY CODE ###

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

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

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

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = []
seen = [False]*(n+1)
while True:
    for i in range(1, n+1):
        if not seen[i]:
            stack = [i]
            break
    else:
        break
    tmp = set()
    while len(stack)>0:
        node = stack.pop()
        tmp.add(node)
        seen[node] = True
        for c_node in friends[node]:
            if seen[c_node]:
                continue
            stack.append(c_node)
    groups.append(tmp)


for i in range(1, n+1):
    for j in groups:
        if i in j:
            print(len(j - set(friends[i]) - set(blocks[i]))-1, end=' ')
            break

### FIXED CODE ###

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

friends = [[] for _ in range(n+1)]
blocks = [[] for _ in range(n+1)]

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

for _ in range(k):
    c, d = map(int, input().split())
    blocks[c].append(d)
    blocks[d].append(c)

groups = [-1]*(n+1)
n_groups = []
g = 0
for i in range(1, n+1):
    if groups[i]>=0:
        continue
    stack = [i]
    cnt = 0
    groups[i] = g
    while len(stack)>0:
        node = stack.pop()
        for c_node in friends[node]:
            if groups[c_node]>=0:
                continue
            stack.append(c_node)
            groups[c_node] = g
            cnt += 1
    n_groups.append(cnt)
    g += 1

ans = []
for i in range(1, n+1):
    tmp = n_groups[groups[i]]
    for j in friends[i]:
        if groups[i] == groups[j]:
            tmp -= 1
    for j in blocks[i]:
        if groups[i] == groups[j]:
            tmp -= 1
    ans.append(tmp)

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

n = int(input())

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

ans = 1

for i in range(n):
    ans *= An[i]

if ans <= 10 ** 18:
    print(ans)
else :
    print(-1)


### FIXED CODE ###


n = int(input())
An = [int(x) for x in input().split()]
An.sort(reverse=True)

if 0 in An:
    print(0)
    exit()

j = 10 ** 18
ans = 1
for i in range(n):
    if ans > j:
        print(-1)
        quit()
    ans *= An[i]

if ans > j :
    print(-1)
    
else :
    print(ans)
### BUGGY CODE ###


def main():
    N,M,Q = map(int, input().split())

    X = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        l,r = map(int, input().split())
        X[l-1][r-1] += 1

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if X[i][j] != 0:
                #if j == i
                C[i][j] = C[i][j-1] + X[i][j]
            else:
                C[i][j] = C[i][j-1]

    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N,M,Q = map(int, input().split())

    X = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(M):
        l,r = map(int, input().split())
        X[l-1][r-1] += 1

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1


    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                tmp += dfs(t) + 1
            L = len(lines[s])
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    ans = 10**10
    for s in range(N-1):
        for t in lines[s]:
            if LL[s] == 1:
                continue
            MEMO = [-1]*N
            MEMO[-1] = 0
            lines[s].remove(t)
            LL[s] -= 1
            tmp = dfs(0)
            #print(s,t,tmp)
            ans = min(ans,tmp)
            lines[s].add(t)
            LL[s] += 1
    print(ans)


### FIXED CODE ###


from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,M = inpl()

if M == N-1: # 一本道
    for _ in range(M):
        s,t = inpl()
    print(M)
else:
    lines = defaultdict(set)
    LL = [0]*N
    for _ in range(M):
        s,t = inpl()
        s -= 1; t -= 1
        lines[s].add(t)
        LL[s] += 1

    def dfs(s):
        global MEMO
        if MEMO[s] != -1:
            return MEMO[s]
        else:
            tmp = 0
            for t in lines[s]:
                if MEMO[t] != -1:
                    tmp += MEMO[t] + 1
                else:
                    tmp += dfs(t) + 1
            MEMO[s] = tmp / LL[s]
            return MEMO[s]

    MEMO = [-1]*N
    MEMO[-1] = 0
    dfs(0)
    koho = [-1]*N
    for s in range(N):
        x = -1
        for t in lines[s]:
            if x < MEMO[t]:
                x = MEMO[t]
                koho[s] = t

    ans = 10**10
    for s in range(N-1):
        t = koho[s]
        if LL[s] == 1 or t == -1:
            continue
        MEMO = [-1]*N
        MEMO[-1] = 0
        lines[s].remove(t)
        LL[s] -= 1
        ans = min(ans,dfs(0))
        lines[s].add(t)
        LL[s] += 1
    print(ans)
### BUGGY CODE ###

N, M = map(int,input().split())
A = sorted(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  B -= 1
  t = False
  while A[B] > C:
    B -= 1
    if B < 0:
      t = True
      break
  if t:
    continue
  if B == 0:
    A = A[1:] + [C]
  else:
    A = A[B+1:] + [C]*(B+1)
print(sum(A))

### FIXED CODE ###

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

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

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

for i in range(K):
  B = [0 for j in range(N)]
  for j in range(N):
    s = A[j]
    # i - A[i] ~ i + A[i]
    for k in range(max(0, j - s), min(j+s+1, N)):
      B[k] += 1
  A = [ B[j] for j in range(N)]
  for j in range(N):
    if A[j] < N:
      break
  else:
    break
print(*A)

### FIXED CODE ###

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

for i in range(K):
  R = [ {} for j in range(N)]

  for j in range(N):
    s = A[j]
    # j - s ~ j + s
    if min(j+s, N-1) in R[max(0, j-s)]:
      R[max(0, j-s)][min(j+s, N-1)] += 1
    else:
      R[max(0, j-s)][min(j+s, N-1)] = 1
        
  # Make Next List
  #print(R)
  L = [0 for j in range(N)]
  t = 0
  for j in range(N):
    r = R[j]
    for k, v in r.items():
      t += v
      L[k] += v
    A[j] = t
    t -= L[j]
    
  if A[0] == N and A[-1] == N:
    for j in range(N):
      if A[j] < N:
        break
    else:
      break
print(*A)