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

N = int(input())
al = [int(a) for a in input().split()]
      
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

l = [0]*N
r = [0]*N

# 左から右
for i in range(N-1):
    if i == 0:
        a = al[i]
        l[i+1] = a
    if i >= 1:
        a = gcd(a, al[i])
        l[i+1] = a

# 右から左
for i in range(N-1):
    if i == 0:
        a = al[::-1][i]
        r[-i-2] = a
    if i >= 1:
        a = gcd(a, al[::-1][i])
        r[-i-2] = a

# 最大公約数リスト
ansl = [0]*N
for i in range(N):
    if i == 0:
        ansl[i] = r[i]
    elif i == N-1:
        ansl[i] = l[i]
    else:
        ansl[i] = gcd(r[i], l[i])
print(max(ansl))

### FIXED CODE ###

N = int(input())
al = [int(a) for a in input().split()]
      
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

l = [0]*N
r = [0]*N

# 左から右
for i in range(N-1):
    if i == 0:
        a = al[i]
        l[i+1] = a
    if i >= 1:
        a = gcd(a, al[i])
        l[i+1] = a

# 右から左
for i in range(N-1):
    if i == 0:
        a = al[-i-1]
        r[-i-2] = a
    if i >= 1:
        a = gcd(a, al[-i-1])
        r[-i-2] = a

# 最大公約数リスト
ansl = [0]*N
for i in range(N):
    if i == 0:
        ansl[i] = r[i]
    elif i == N-1:
        ansl[i] = l[i]
    else:
        ansl[i] = gcd(r[i], l[i])
print(max(ansl))
### BUGGY CODE ###

import itertools

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

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

ans = 1000000

for i in itertools.permutations(prices, k):
    ans = min(ans, sum(i))

print(ans)

### FIXED CODE ###

import itertools

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

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

prices = sorted(prices)

print(sum(prices[:k]))
### BUGGY CODE ###

n  =int(input())
s = input()

cnt = 0

for a in range(10):
    for b in range(10):
        for c in range(10):
            flag = False
            for j in range(n):
                if s[j] == str(a):
                    for k in range(j+1,n):
                        if s[k] == str(b):
                            for l in range(k+1,n):
                                if s[l] == str(c):
                                    flag = True
                                    cnt+=1
                                    #print(a,b,c)
                                    break       
                                if flag:
                                    break
                                                               
                            if flag:
                                break
                        if flag:
                            break
                if flag:
                    break
                    
               
        
print(cnt)

### FIXED CODE ###

n  =int(input())
s = input()

cnt = 0

for a in range(10):
    s_index = s.find(str(a)) 
    if s_index == -1:
        continue##この先はやらない
    for b in range(10):
        t_index = s.find(str(b),s_index+1)
        if t_index==-1:
            continue
        for c in range(10):
            u_index = s.find(str(c),t_index+1)
            if u_index != -1:
                cnt+=1
                    
               
        
print(cnt)
### BUGGY CODE ###

N = int(input())

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

for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

import collections

N = int(input())

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

c = collections.Counter(A)

for i in range(N):
    print(c[i+1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  #A=list(map(int,input().strip("\n").split()))
  A=input().strip("\n")
  q=int(input())
  ans=''
  for i in range(q):
    #b,c=map(int,input().strip("\n").split())
    b,c=input().strip("\n").split()
    A=A.replace(b,c)
    ans+=str(eval(A.replace(" ","+")))
    if i==q-1:
      print(ans)
    else:
      ans+="\n"


### FIXED CODE ###

import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n=int(input())
  A_str=input().strip("\n")
  A=A_str.split()
  q=int(input())

  C={}
  for a in A:
    if a in C:
      C[a]+=1
    else:
      C[a]=1
  
  def rep(b,c):
    if c in C:
      C[c]+=C[b]
    else:
      C[c]=C[b] 
    C[b]=0
    #print(b,c,C)

  Ans=[]
  ans=''
  b,c=input().strip("\n").split()
  #tmp=eval(A_str.replace(b,c).replace(" ","+"))
  tmp=0
  hoge=map(int,A)
  for a in hoge:
    if str(a)==b:
      tmp+=int(c)
    else:
      tmp+=a
  #ans+=str(tmp)
  #ans+="\n"
  Ans.append(tmp)
  if b in C:
    rep(b,c)
  for i in range(1,q-1):
    b,c=input().strip("\n").split()
    if b in C:
      tmp+=(int(c)-int(b))*C[b]
      rep(b,c)
    #ans+=str(tmp)+"\n"
    Ans.append(tmp)
  b,c=input().strip("\n").split()
  if b in C:
    tmp+=(int(c)-int(b))*C[b]
  #ans+=str(tmp)
  Ans.append(tmp)
  #print(ans)
  for ans in Ans:
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n):
    for j in range(i, n):
        if (sum(a[i:j+1]) == 0):
            cnt += 1 
print(cnt)    

### FIXED CODE ###

'''
https://beta.atcoder.jp/contests/agc023/submissions/2426081
'''
n = int(input())
A = map(int, input().split())
B = {0:1}
s = 0
ans = 0
for a in A:
    s += a
    B_s = B.get(s, 0) 
    ans += B_s
    B[s] = B_s + 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
max = 0
b_int = 0
if n < 5:
  for i in range(0,n):
    if b_int == a[0]:
      p = a.pop(0)
      a.append(p)
    else:
      p = a.pop(0)
      b_int = p
      x = list_euclid(a)
      if max < x:
        max = x
      a.append(p)
else:
  for i in range(0,n):
    if b_int == a[0]:
      p = a.pop(0)
      a.append(p)
    else:
      p = a.pop(0)
      b_int = p
      k = n // 2
      x = 0
      y = list_euclid(a[0:k])
      if y == 1:
        x = 1
      else:
        z = list_euclid(a[k:n-1])
        x = euclid(y, z)
      if max < x:
        max = x
      a.append(p)
print(max)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###

n = int(input())
ll = list(map(int,input().split()))
mm = []
pp = n
i = 0
for i in range(n):
    try:
        mm.append(ll[-1-2*i])
        ll[-1-2*i] = -1
    except:
        pass

    
for i in range(len(ll)):
    if ll[i] > -1:
        mm.append(ll[i])
    else:
        None
        
sss = ''
for i in range(len(mm)):
    if i != 0:
        sss = sss + ' ' + str(mm[i])
    else:
        sss = sss + str(mm[i])
        
print(sss)

### FIXED CODE ###

n = int(input())
ll = list(map(int,input().split()))
mm = []
pp = n
i = 0
for i in range(n):
    try:
        mm.append(str(ll[-1-2*i]))
        ll[-1-2*i] = '-1'
    except:
        pass

    
for i in range(len(ll)):
    if ll[i] != '-1':
        mm.append(str(ll[i]))
    else:
        None
        
sss = ''
for i in mm:
    print(i, end= ' ')
### BUGGY CODE ###

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

    m = 10 ** 9 + 7
    a = [i % m for i in a]
    sum_a = [a[i] * a[j] % m for i in range(n) for j in range(i+1, n)]
    ans = sum(sum_a) % m
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


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

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    if i+1 not in a:
        dp[i+1] += dp[i]
    if i<n-1 and i+2 not in a:
        dp[i+2] += dp[i]
print(dp[-1]%(10**9+7))


### FIXED CODE ###

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a = set(a)
dp = [0]*(n+1)
dp[0] = 1
for i in range(n):
    if i+1 not in a:
        dp[i+1] += dp[i]
    if i<n-1 and i+2 not in a:
        dp[i+2] += dp[i]
print(dp[-1]%(10**9+7))
### BUGGY CODE ###

from bisect import bisect_left
s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    dp[i][0] = 0
for j in range(len(t)):
    dp[0][j] = 0
for i in range(0, len(s)):
    for j in range(0, len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
dpt = list(map(list, zip(*dp)))
i = len(s)
j = len(t)
ans = ''
for a in range(dp[len(s)][len(t)], 0, -1):
    jj = bisect_left(dp[i], a)
    ii = bisect_left(dpt[j], a)
    ans += t[jj - 1]
    i = ii - 1
    j = jj - 1
print(ans[::-1])

### FIXED CODE ###

s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    dp[i][0] = 0
for j in range(len(t)):
    dp[0][j] = 0
for i in range(0, len(s)):
    for j in range(0, len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])
i = len(s)
j = len(t)
ans = ''
while True:
    if s[i - 1] == t[j - 1]:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1
    if dp[i][j] == dp[i][j - 1]:
        j -= 1
    elif dp[i][j] == dp[i - 1][j]:
        i -= 1
    if i <= 0 or j <= 0:
        break
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
t = input()
s_idx = [""]*26
t_idx = [""]*26
for i in range(len(s)):
    s_idx[ord(s[i])-97] += str(i)
for i in range(len(s)):
    t_idx[ord(t[i])-97] += str(i)
s_idx.sort()
t_idx.sort()
if s_idx == t_idx:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
t = input()
s_idx = [[] for _ in range(26)]
t_idx = [[] for _ in range(26)]
for i in range(len(s)):
    s_idx[ord(s[i])-97].append(i)
visit = []
for i in range(26):
    cnt = 0
    for j in s_idx[i]:
        if cnt == 0 and t[j] in visit:
            print("No")
            exit()
        if cnt == 0:
            visit.append(t[j])
            cnt += 1
        else:
            if t[j] != visit[-1]:
                print("No")
                exit()
print("Yes")
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[]
dp.append(0)
dp.append(abs(h[1]-h[0]))
for i in range(2,n):
  dp.append(min(dp[j]+abs(h[i]-h[j]) for j in range(max(i-k,0),i)))
print(dp[n-1])

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
	dp=[0]*N
	for i in range(1,N):
		dp[i] = min(dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i))
	print(dp[N-1])
main()
### BUGGY CODE ###

def lucas(i):
  if i == 0:
    return 2
  elif i == 1:
    return 1
  else:
    return lucas(i-1) + lucas(i-2)
  
N = int(input())
print(lucas(N))

### FIXED CODE ###

N = int(input())
L = [2, 1]
for i in range(2, N+1):
  L.append(L[i-1]+L[i-2])
print(L[N])
### BUGGY CODE ###

Dy = [1,0,-1,0]
Dx = [0,-1,0,1]

H, W, K = map(int, input().split())
A = [input() for _ in range(H)]
Closed = [[False]*W for _ in range(H)]
for y, a in enumerate(A):
    for x, aa in enumerate(a):
        if aa=="S":
            ys, xs = y, x
q = [(ys, xs)]
Closed[ys][xs] = True
reachable = [(ys, xs)]
for _ in range(K):
    q_new = []
    for y_old, x_old in q:
        for dy, dx in zip(Dy, Dx):
            y, x = y_old + dy, x_old + dx
            if not (0<=y<H and 0<=x<W):
                continue
            if not Closed[y][x] and A[y][x]==".":
                Closed[y][x] = True
                reachable.append((y, x))
                q_new.append((y, x))
    q = q_new
mi = float("inf")
for y, x in reachable:
    mi = min(mi, x, y, W-1-x, H-1-y)
print((mi-1)//K+2)


### FIXED CODE ###

def main():
    Dy = [1,0,-1,0]
    Dx = [0,-1,0,1]
    
    H, W, K = map(int, input().split())
    A = [input() for _ in range(H)]
    Closed = [[False]*W for _ in range(H)]
    for y, a in enumerate(A):
        for x, aa in enumerate(a):
            if aa=="S":
                ys, xs = y, x
    q = [(ys, xs)]
    Closed[ys][xs] = True
    reachable = [(ys, xs)]
    for _ in range(K):
        q_new = []
        for y_old, x_old in q:
            for dy, dx in zip(Dy, Dx):
                y, x = y_old + dy, x_old + dx
                if not (0<=y<H and 0<=x<W):
                    continue
                if not Closed[y][x] and A[y][x]==".":
                    Closed[y][x] = True
                    reachable.append((y, x))
                    q_new.append((y, x))
        q = q_new
    mi = float("inf")
    for y, x in reachable:
        mi = min(mi, x, y, W-1-x, H-1-y)
    print((mi-1)//K+2)

main()
### BUGGY CODE ###

import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=mkns(a[i],ss[i],pm)
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            nn+=1
    # def isunnec(i):
    #     for j in range(i+1,N):
    #         if a[j]>=K:
    #             return False
    #         ss[i]=mkns(a[j],ss[i],pm)
    #     # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
    #     if ss[i]&mask(K-c)==0:
    #         return True
    #     return False
    # nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()


### FIXED CODE ###

#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)
### BUGGY CODE ###

from sys import exit
import math
x,y = map(int, input().split())
seppen = x + y
def combinations_count(n, r):

    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
if seppen%3 != 0:
    print(0)
    exit()
else:
    dan = seppen/3
    gen_y = seppen/3
    kyori = y - gen_y
    if kyori < 0 or kyori > dan:
        print(0)
    else:
        print(combinations_count(dan, kyori)%(10**9+7))

### FIXED CODE ###

from sys import exit
import math
x,y = map(int, input().split())
seppen = x + y

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


if seppen%3 != 0:
    print(0)
    exit()
else:
    dan = int(seppen/3)
    kyori = y - dan

    mod = 10**9+7 #出力の制限
    N = dan
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル

    for i in range( 2, N + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    if kyori < 0 or kyori > dan:
        print(0)
    else:
        a = cmb(dan,kyori,mod)
        print(a)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
#累積和を木に拡張する
N, Q = map(int, input().split())

graph = [[] for i in range(N)]
score = [0 for _ in range(N)]

def dfs(now, prev):

    for adj in graph[now]:
        if adj == prev:
            continue
        score[adj] += score[now]
        dfs(adj, now)

    return

for i in range(1, N):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

query = [0] * N
for i in range(Q):
    p, x = map(int, input().split())

    score[p-1] += x

dfs(0, -1)

for p in score:
    print(p)


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
#累積和を木に拡張する
N, Q = map(int, input().split())

graph = [[] for i in range(N)]
score = [0 for _ in range(N)]

def dfs(now, prev):

    for adj in graph[now]:
        if adj == prev:
            continue
        score[adj] += score[now]
        dfs(adj, now)

    return

for i in range(1, N):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

query = [0] * N
for i in range(Q):
    p, x = map(int, input().split())

    score[p-1] += x

dfs(0, -1)

for p in score:
    print(p)
### BUGGY CODE ###

def light(y,x):
    global g
    if not g[y][x]:
        return 0
    else:
        x0,y0=x,y
        L,R,U,D=0,0,0,0
        while x>=1 and g[y][x-1]:
            L+=1
            x-=1
        x,y=x0,y0
        while x<=W-2 and g[y][x+1]:
            R+=1
            x+=1
        x,y=x0,y0
        while y>=1 and g[y-1][x]:
            U+=1
            y-=1
        x,y=x0,y0
        while y<=H-2 and g[y+1][x]:
            D+=1
            y+=1
        return 1+L+R+U+D
        
H,W=map(int,input().split())
g=[[True for j in range(W)] for i in range(H)] # 障害物がなければTrue
for i in range(H):
    S=input()
    for j in range(W):
        if S[j]=='#':
            g[i][j]=False
D=[[0 for j in range(W)] for i in range(H)]
U=[[0 for j in range(W)] for i in range(H)]
R=[[0 for j in range(W)] for i in range(H)]
L=[[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if j==0:
            L[i][j]=1 if g[i][j] else 0
        else:
            L[i][j]=L[i][j-1]+1 if g[i][j] else 0
    for j in reversed(range(W)):
        if j==W-1:
            R[i][j]=1 if g[i][j] else 0
        else:
            R[i][j]=R[i][j+1]+1 if g[i][j] else 0

for j in range(W):
    for i in range(H):
        if i==0:
            U[i][j]=1 if g[i][j] else 0
        else:
            U[i][j]=U[i-1][j]+1 if g[i][j] else 0
    for i in reversed(range(H)):
        if i==H-1:
            D[i][j]=1 if g[i][j] else 0
        else:
            D[i][j]=D[i+1][j]+1 if g[i][j] else 0

ans=0

for i in range(H):
    for j in range(W):
        if g[i][j]:
            ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
            
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
s=[]
for i in range(H):
    si=[]
    Si=input()
    for j in range(W):
        si.append(Si[j]=='.')
    s.append(si)

# 左に照らした場合 行ごとに見てゆく
L=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and s[i][j]:
            L[i][j]=1
        elif s[i][j]:
            L[i][j]=L[i][j-1]+1

# 右に照らした場合 行ごとに見てゆく
R=[[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in reversed(range(W)):
        if j==W-1 and s[i][j]:
            R[i][j]=1
        elif s[i][j]:
            R[i][j]=R[i][j+1]+1

# 上に照らした場合 列ごとに見てゆく
U=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in range(H):
        if i==0 and s[i][j]:
            U[i][j]=1
        elif s[i][j]:
            U[i][j]=U[i-1][j]+1

# 下に照らした場合 列ごとに見てゆく
D=[[0 for j in range(W)] for i in range(H)]
for j in range(W):
    for i in reversed(range(H)):
        if i==H-1 and s[i][j]:
            D[i][j]=1
        elif s[i][j]:
            D[i][j]=D[i+1][j]+1

ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

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

import sys
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=A+B
C.sort()
for i in range(len(C)) :
    if sum(C[:i])>K :
        print(i-1)
        sys.exit()
print(len(C))

### FIXED CODE ###

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

a=[0]
b=[0]

for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
j=M
ans=0
for i in range(N+1):#aは小さい方から
    if a[i]>K:    #a[0]=0なのでいきなりbreakすることはない
        break
    while b[j]>K-a[i] : #bは大きい方から
        j-=1            #j,ansの値は次のループに引き継がれる
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

def resolve():
    import sys

    input = sys.stdin.readline
    N, M = map(int, input().split())

    import bisect

    ABs = [[] for _ in range(M + 1)]
    for i in range(N):
        A, B = map(int, input().split())
        if A <= M:
            ABs[A].append(B)
    ABs[0].sort()

    As = 0
    for i in range(M + 1):
        if i > 0:
            for b in ABs[i]:
                bisect.insort_left(ABs[0], b)
        if len(ABs[0]) > 0:
            As += ABs[0].pop()
    print(As)

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        ABs[A].append(B)
ABs[0].sort()

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)
### BUGGY CODE ###

n = int(input())
command = [input().split() for i in range(n)]
ans = []

for i in range(n):
    if command[i][0] == "insert":
        ans.insert(0, command[i][1])
    elif ans == []:
        continue
    elif command[i][0] == "delete":
        try:
            ans.remove(command[i][1])
        except:
            continue
    elif command[i][0] == "deleteFirst":
        ans.pop(0)
    else:
        ans.pop()

print (' '.join(ans))

### FIXED CODE ###

# -*- coding:utf-8 -*-
import collections
n = int(input())
ans = collections.deque()

for i in range(n):
    command = input().split()
    if command[0] == "insert":
        ans.appendleft(command[1])
    elif ans == []:
        continue
    elif command[0] == "delete":
        try:
            ans.remove(command[1])
        except:
            pass
    elif command[0] == "deleteFirst":
        ans.popleft()
    else:
        ans.pop()

print (' '.join(ans))
### BUGGY CODE ###

N = int(input())
line = list(input())

# print(line)
bottom_w = N
top = 0
count = 0
while(bottom_w > top):
    for i in reversed(range(bottom_w)):
        if(line[i]=='R'):
            bottom_w = i
            break
    if(line[-1]=='W' and bottom_w == N):
        print(0)
        exit()
    for i in range(top,N):
        if(line[i]=='W' and bottom_w > i):
            # print("line",i,line[i])
            # print("swap",i,bottom_w)
            count += 1
            line[bottom_w] = 'W'
            top = i+1
            break
print(count)


### FIXED CODE ###

N = int(input())
line = list(input())

# print(line)
bottom_w = N
top = 0
count = 0
while(bottom_w > top):
    for i in reversed(range(bottom_w)):
        if(line[i]=='R'):
            bottom_w = i
            break

    if(line[-1]=='W' and bottom_w == N):
        print(0)
        exit()
    if(bottom_w <= top):
        break
    for i in range(top,N):
        if(i == N-1):
            print(count)
            exit()
        if(line[i]=='W' and bottom_w > i):
            # print("line",i,line[i])
            # print("swap",i,bottom_w)
            count += 1
            line[bottom_w] = 'W'
            top = i+1
            break
print(count)