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

class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      self.Tree[s1]=s2
      self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      
N,M=map(int,input().split())
List=[[int(i) for i in input().split()] for i in range(M)] 
wuf=WeightsUnionfind(N)
F=0
for l in List:
  wuf.unite(l[0]-1,l[1]-1,l[2])
if wuf.wrong==1:
  print("No")
else:
  print("Yes")
    

  
      
    
      
      

### FIXED CODE ###

class WeightsUnionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.dWeights=[0]*n
    self.rank=[0]*n
    self.wrong=0

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.dWeights[x]=self.weigh(x)
      self.Tree[x]=root
      return root
  
  def weigh(self,x):
    if x==self.Tree[x]:
      return 0
    else:
      w=self.weigh(self.Tree[x])+self.dWeights[x]
      return w

  def unite(self,x,y,w):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      if self.weigh(y)-self.weigh(x)!=w:
        self.wrong=1
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
        self.dWeights[s1]=self.weigh(y)-self.weigh(x)-w
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        self.dWeights[s2]=self.weigh(x)-self.weigh(y)+w
          
N,M=map(int,input().split())
wuf=WeightsUnionfind(N)
F=0
for m in range(M):
  l,r,d=map(int,input().split())
  wuf.unite(l-1,r-1,d)
if wuf.wrong==1:
  print("No")
else:
  print("Yes")
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

for i in range(N):
    update(i,ord(S[i]))

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline
from collections import deque

n,m = map(int,input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
cnt = [n]*n
def dfs(now, prev,c):
    for next in g[now]:
        if next != prev:
          if cnt[next] > c:
            ans[next] = now+1
            cnt[next] = c
            dfs(next, now,c+1)
            
dfs(0,-1,1)

for i in ans[1:]:
  if i == -1:
    print('No')
    exit()
print('Yes')
for i in ans[1:]:
  print(i)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
from collections import deque

que = deque()
que.append((0,1))
chk = [False]*n
chk[0] =True
cnt = 1
while que:
    now,p = que.popleft()
    if cnt == n:
      break
    for i in g[now]:
        if not chk[i]:
          ans[i] = p
          chk[i] = True
          cnt += 1
          que.append((i,i+1))

if cnt!=n:
  print('No')
  exit()
  
print('Yes')
for i in ans[1:]:
  print(i)
### BUGGY CODE ###

#閉路判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
if find_loop(n*n,edge,0)==False:print(-1);exit()
t=find_loop(n*n,edge,1)
ans=[1]*n*n
for i in t:
  for j in edge[i]:ans[j]=max(ans[j],ans[i]+1)
print(max(ans))

### FIXED CODE ###

#閉路判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
if find_loop(n*n,edge,0)==False:print(-1);exit()
t=find_loop(n*n,edge,1)
ans=[1]*n*n
for i in t:
  for j in edge[i]:ans[j]=max(ans[j],ans[i]+1)
print(max(ans))
### BUGGY CODE ###

from collections import defaultdict,deque
import copy
import numpy as np
import bisect

N = int(input())
A = list(map(int,input().split()))
graph = defaultdict(deque)
for _ in range(0,N-1):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

arrive = [False] * (N+1)
dp_dict = [deque([]) for _ in range(N)]
dp_dict[0].append(A[0])


ans = [None] *(N+1)
def dfs(s):
    stack = deque([s])
    while stack:
        v = stack[-1]
        arrive[v] = True
        if graph[v]:
            w = graph[v].pop()
            if arrive[w] == False:
                tar = A[w-1]
                dp = dp_dict[v-1].copy()
                if tar > dp[-1]:
                    dp.append(tar)
                else:
                    dp[bisect.bisect_left(dp, tar)] = tar
                ans[w] = len(dp)
                dp_dict[w-1] = dp
                stack.append(w)

        else:
            stack.pop()


dfs(1)
ans[1] = 1
for i in ans[1::]:
    print(i)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = tuple(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
 
ans = [-1] * (N + 1)
inf = 10**18
LIS = [inf] * (N + 1)
 
def DFS(s, parent=0):
    a = A[s - 1]
    i = bisect.bisect_left(LIS, a)
    v = LIS[i]
    LIS[i] = a
    ans[s] = bisect.bisect_left(LIS, inf)
    for t in graph[s]:
        if t == parent:
            continue
        DFS(t, s)
    LIS[i] = v
    return
 
DFS(1)
print(*ans[1:], sep="\n")
### BUGGY CODE ###

N,M = [int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()])
BC = []
for _ in range(M):
    BC.append([int(i) for i in input().split()])
BC = sorted(BC,reverse=True)
for m in range(M):
    for b in range(BC[m][0]):
        if A[b] > BC[m][1]:
            break
        else:
            A[b] = BC[m][1]
    A = sorted(A)
print(sum(A))

### FIXED CODE ###

N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
BC = []
for m in range(M):
    BC.append([int(i) for i in input().split()])
    if BC[m][0] > N:
        BC[m][0] = N
BC = sorted(BC,reverse=True,key=lambda x: x[1])
change_list = []
for m in range(M):
    change_list.extend([BC[m][1] for _ in range(BC[m][0])])
    if len(change_list) >= N:
        change_list = change_list[0:N]
        break
A.extend(change_list)
A = sorted(A,reverse=True)
print(sum(A[0:N]))
### BUGGY CODE ###

import numpy as np
A,B = list(map(int,input().split()))
if A == 1:
  print(B)
  exit()
if B == 1:
  print(A)
  exit()
C = A*B
D = []
for i in range(C,1,-1):
  if A % i == 0 and B % i == 0:
    D.append(i)
    A = A // i
    B = B // i
    C = A*B
if len(D) != 0:
  p = np.prod(D)
  C = C*p
print(C)

### FIXED CODE ###

import math
import numpy as np
A,B = list(map(int,input().split()))
if A == 1:
  print(B)
  exit()
if B == 1:
  print(A)
  exit()
C = A*B
D = []
for i in range(int(math.sqrt(C)),1,-1):
  if A % i == 0 and B % i == 0:
    D.append(i)
    A = A // i
    B = B // i
    C = A*B
if len(D) != 0:
  p = np.prod(D)
  C = C*p
print(C)
### BUGGY CODE ###

s = list(input())
ans = [0]*len(s)
for i in range(len(s)):
    cnt = 0
    if s[i] == "R":
        while s[i + cnt] == "R":
            cnt += 1
        if cnt%2 == 0:
            ans[i + cnt] += 1
        else:
            ans[i + cnt - 1] += 1
    else:
        while s[i - cnt] == "L":
            cnt += 1
        if cnt%2 == 0:
            ans[i - cnt] += 1
        else:
            ans[i - cnt + 1] += 1

an = [str(i) for i in ans]
print(" ".join(an))


### FIXED CODE ###

s = list(input())
ans = [0]*len(s)

i = 0
while i != len(s):
    cnt1 = 0
    cnt2 = 0
    while s[i + cnt1] == "R":
        cnt1 += 1
    ans[i + cnt1] += cnt1//2
    ans[i + cnt1 - 1] += cnt1//2 + cnt1%2
    while s[i + cnt1 + cnt2] == "L":
        cnt2 += 1
        if i + cnt1 + cnt2 == len(s):
            break
    ans[i + cnt1] += cnt2//2 + cnt2%2
    ans[i + cnt1 - 1] += cnt2//2
    i += cnt1 + cnt2

an = [str(i) for i in ans]
print(" ".join(an))
### BUGGY CODE ###

def solve():
    dp = [0]*(n+2)
    for x in range(1,151):
        for y in range(1,151):
            for z in range(1,151):
                a = x**2+y**2+z**2+x*y+y*z+z*x
                if a<=n:
                    dp[a] += 1
    for i in range(1,n+1):
        print(dp[i])                

if __name__=="__main__":
    n = int(input())
    solve()


### FIXED CODE ###

N = int(input())
ls = [0]*(N+2)
 
for i in range(1,151):
    for j in range(1,151):
        for k in range(1,151):
            t = i*i + j*j + k*k + i*j + j*k + k*i 
            if t <= N :
                ls[t] += 1
 
for p in range(1,N+1):
    print(ls[p])
### BUGGY CODE ###

n = int(input())
L = sum([list(map(int, input().split())) for i in range(n)], [])
count = 0
next = 0
NG = [1]
while True:
  if L[next] in NG:
    print(-1)
    quit()
  elif L[next] == 2:
    print(count+1)
    quit()
  else:
    NG.append(L[next])
    next = L[next]-1
    count += 1

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
cur = 1
cnt = 0
while True:
    if cur == 2:
        print(cnt)
        exit()
    elif cnt > n:
        print(-1)
        exit()
    else:
        cur = a[cur - 1]
        cnt += 1
### BUGGY CODE ###

def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    dp = [0,0,0,0]
    mod = 10**9 + 7
    for i in s:
        if i=="A":
            dp[0] += 3**(dp[3])
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += 3**(dp[3]) 
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

if __name__=="__main__":
    s = getval()
    main(s)

### FIXED CODE ###

def getval():
    s = input()
    return s
    
def main(s):
    #dp for "a","ab","abc"
    mod = 10**9 + 7
    dp = [0,0,0,0]
    p3 = [1]
    for i in range(len(s)):
        p3.append((3*p3[i])%mod)
    for i in s:
        if i=="A":
            dp[0] += p3[dp[3]]
            dp[0] %= mod
        elif i=="B":
            dp[1] += dp[0]
            dp[1] %= mod
        elif i=="C":
            dp[2] += dp[1]
            dp[2] %= mod
        else:
            temp1 = dp[0]*2
            temp2 = dp[1]*2
            temp3 = dp[2]*2
            dp[2] += dp[1]
            dp[1] += dp[0]
            dp[0] += p3[dp[3]]
            dp[2] += temp3
            dp[1] += temp2
            dp[0] += temp1
            dp[3] += 1
            for j in range(3):
                dp[j] %= mod
            #print(dp)
    print(dp[2])

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

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
  print(A.index(i)+1,end=" ")

### FIXED CODE ###

from operator import itemgetter
N=int(input())
A=list(map(int,input().split()))
B=[(i+1,A[i]) for i in range(N)]
B=sorted(B,key=itemgetter(1))
for k in range(N):
  print(B[k][0],end=" ")
### BUGGY CODE ###

from itertools import permutations
n=int(input())
N=list(map(int,input().split()))
ans=[]
for i in list(permutations(N)):
    flag=1
    i=list(i)
    i.insert(0,i[-1])
    i.append(i[1])
    for j in range(1,n):
        if i[j]!=i[j-1]^i[j+1]:
            flag=0
            break
    ans.append(flag)

if 1 in ans:print("Yes")
else:print("No")

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
temp = 0
for i in A:
    temp = temp ^ i
if(temp == 0):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def Mo(n,q,c,qi,base):
    ans = [0]*q
    ln = [-1]*(n+1)

    #BITの構成
    BIT = [0]*(n+1)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    #Rが小さい方から見ていく,BITによる累積和の処理を含む
    pr = 0
    for ist in qi:
        i = ist%(base)
        l = (ist//(base))%(base)
        r = ist//(base)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        ans[i] = BIT_query(r)-BIT_query(l-1)
    return ans

def main():
    n,q = map(int,ipt().split())
    c = [int(i) for i in ipt().split()]
    qi = []
    base = 10**6+1
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*(base**2)+l*base+i)
    qi.sort()

    ans = Mo(n,q,c,qi,10**6+1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*((10**6+1)**2)+l*(10**6+1)+i)

    qi.sort()

    ans = [0]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%(10**6+1)
        l = (ist//(10**6+1))%(10**6+1)
        r = ist//(10**6+1)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)


    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()
### BUGGY CODE ###

n, k = (int(x) for x in input().split())
p = [int(x) for x in input().split()]
p_sum = [sum(p[i:i+k]) for i in range(len(p)-k+1)]
idx = p_sum.index(max(p_sum))
ans = 0
for p_i in p[idx:idx+k]:
    b = 1 / p_i
    for i in range(1, int(p_i+1)):
        ans += i * b
print(ans)

### FIXED CODE ###

n, k = (int(x) for x in input().split())
p = [int(x) / 2 + 0.5 for x in input().split()]
ans_i = ans = sum(p[:k])
i = 0
while i < n - k:
    ans_i = ans_i - p[i] + p[i+k]
    ans = max(ans, ans_i)
    i += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
MOD = 10 ** 9 + 7

C = [[0] * 4005 for _ in range(4005)]

def init():
    C[0][0] = 1
    for i in range(4002):
        for j in range(0, i+1):
            C[i+1][j] += C[i][j]
            C[i+1][j] %= MOD
            C[i+1][j+1] += C[i][j]
            C[i+1][j+1] %= MOD
            

def comb(N, K):
    return C[N][K]

def f2(N, K):
    return comb(N+K-1, K-1)

def f(N, K):
    if (N < K): return 0
    if N == 0 and K == 0: return 1
    if (K < 1): return 0
    return f2(N-K, K)


init()

for i in range(1,K+1):
    blue = f(K, i)
    red = 0
    red += f(N-K, i-1)
    red += f(N-K, i) * 2 % MOD
    red += f(N-K, i+1) % MOD
    
    print(red * blue % MOD)

### FIXED CODE ###

from operator import mul
from functools import reduce

N, K = map(int, input().split())
MOD = 10 ** 9 + 7


def comb(N, R):
    R = min(N-R, R)
    if R == 0: return 1
    over = reduce(mul, range(N, N - R, -1))
    under = reduce(mul, range(1,R + 1))
    return over // under % MOD


def f2(N, K):
    return comb(N+K-1, K-1)

def f(N, K):
    if (N < K): return 0
    if N == 0 and K == 0: return 1
    if (K < 1): return 0
    return f2(N-K, K)


for i in range(1,K+1):
    blue = f(K, i)
    red = 0
    red += f(N-K, i-1)
    red += f(N-K, i) * 2 % MOD
    red += f(N-K, i+1) % MOD
    
    print(red * blue % MOD)
### BUGGY CODE ###

N,H = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

import numpy
A = numpy.array(A)
B = numpy.array(B)
AsortA = numpy.sort(A)[::-1]
BsortB = numpy.sort(B)[::-1]

ans = 0
maxattack = AsortA[0]
throw = BsortB[maxattack < BsortB]
if(sum(throw) >= H):
    for i in range(1,len(throw) + 1):
        if(sum(throw[:i]) >= H):
            ans = i
            break
else:
    resH = H - sum(throw)
    ak = int(numpy.ceil(resH/maxattack))
    ans = ak + len(throw)
    
print(ans)

### FIXED CODE ###

N,H = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

import numpy
A = numpy.array(A)
B = numpy.array(B)
AsortA = numpy.sort(A)[::-1]
BsortB = numpy.sort(B)[::-1]

ans = 0
maxattack = AsortA[0]
throw = BsortB[maxattack < BsortB]
if(sum(throw) >= H):
    ak = 0
    for i in range(len(throw)):
        ak += throw[i]
        if(ak >= H):
            ans = i+1
            break
else:
    resH = H - sum(throw)
    ak = int(numpy.ceil(resH/maxattack))
    ans = ak + len(throw)
    
print(ans)
### BUGGY CODE ###

from math import inf
n,h=map(int,input().split())
l=[int(i) for i in input().split()]
Inf=10**10
dp=[Inf]*n
dp[0]=0
dp[1]=abs(l[1]-l[0])
for i in range(2,n):
    for j in range(1,min(i,h)+1):
        dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))
print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    INF = 10**10
    DP = [INF]*N
    DP[0] = 0
    DP[1] = abs(h[1]-h[0])
    for i in range(2,N):
        DP[i] = min(DP[i-j] + abs(h[i-j]-h[i]) for j in range(1,min(K,i)+1))
    print(DP[-1])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
    b, c = map(int, input().split())
    for i in range(N):
        if b > 0:
            if A[i] < c:
                A[i] = c
                b -= 1
    A.sort()

print(sum(A))
     






### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = LIST()
L = [LIST() for i in range(M)]
L = sorted(L, key=lambda x : x[1], reverse=True)
default_sum = sum(A)

heapq.heapify(A)  # リストを優先度付きキューへ

for max_cnt, target in L:
    cnt = 0
    while cnt < max_cnt and len(A) != 0:
        min_num = heapq.heappop(A) # pop min
        default_sum += max(target - min_num, 0)
        cnt += 1
    
print(default_sum)



    

exit()
print(heapq.heappop(a))  # 最小値の取り出し

heapq.heappush(a, -2)  # 要素の挿入
print(a)
for i in range(M):
    a = heapq.heappop(A) * (-1)
    a = a // 2
    heapq.heappush(A, -a)
A = list(map(lambda x: x * (-1), A))
print(sum(A))