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

import copy
n=int(input())
A=[int(input()) for _ in range(n)]
for i in range(len(A)):
    B=copy.copy(A)
    del B[i]
    print(max(B))

### FIXED CODE ###

n=int(input())
A=[int(input()) for _ in range(n)]
ma=max(A)
ma_i=A.index(ma)
for i in range(n):
    if i==ma_i:
        print(max(A[:i]+A[i+1:]))
    else:
        print(ma)
### BUGGY CODE ###

from collections import deque

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

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a - 1, b - 1, P - c))

# preprocess
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
for a, b, c in ABC:
    to[a].append(b)
    fr[b].append(a)

visitable_s = [False] * N
q = deque()
q.append(0)
visitable_s[0] = True
while len(q):
    a = q.pop()
    for b in to[a]:
        if not visitable_s[b]:
            visitable_s[b] = True
            q.append(b)

visitable_g = [False] * N
q = deque()
q.append(N - 1)
visitable_g[N - 1] = True
while len(q):
    a = q.pop()
    for b in fr[a]:
        if not visitable_g[b]:
            visitable_g[b] = True
            q.append(b)

visitable = [visitable_s[i] and visitable_g[i] for i in range(N)]
inf = float("inf")
d = [inf] * N
d[0] = 0

# Bellman-Ford
for i in range(N):
    for a, b, c in ABC:
        if not visitable[a] or not visitable[b]:
            continue
        if d[b] <= d[a] + c:
            continue
        if i == N - 1:
            print(-1)
            exit()
        d[b] = d[a] + c
ans = d[N - 1]
print(max(0, -d[N - 1]))


### FIXED CODE ###

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

ABC = []
for _ in range(M):
    a, b, c = map(int, input().split())
    ABC.append((a - 1, b - 1, P - c))

inf = float("inf")
d = [inf] * N
d[0] = 0

# Bellman-Ford
for i in range(N):
    for a, b, c in ABC:
        if d[b] <= d[a] + c:
            continue
        d[b] = d[a] + c
ans = d[N - 1]
for i in range(N):
    for a, b, c in ABC:
        if d[b] <= d[a] + c:
            continue
        d[b] = d[a] + c
if ans != d[N - 1]:
    print(-1)
else:
    print(max(0, -d[N - 1]))
### BUGGY CODE ###

N = int(input())

l = []
c = 0

for i in range(N):
    text = "".join(sorted(list(input())))
    l.append(text)
    l = sorted(l)
    
for j in range(N):
    for k in range(j+1,N):
        if l[j] == l[k]:
            c += 1
        else:
            break

print(c)

### FIXED CODE ###

N = int(input())

ans = 0
d = {}

for i in range(N):
    txt = "".join(sorted(input()))
    d.setdefault(txt,0)
    
    ans += d[txt]
    d[txt] += 1
    
print(ans)
### BUGGY CODE ###

N = int(input())
lis = []
X = []
ans = []
for i in range(N):
    x,l = map(int, input().split(" "))
    lis.append((x-l,x+l))
    X.append(x)
s = []
for i in range(N):
    cnt = 0
    for j,v in enumerate(lis):
        a,b = v
        if i == j:
            continue
        else:
            if a < X[i] < b:
                cnt += 1
    if cnt == 0:
        ans.append(lis[i])
    if cnt == 1:
        s.append(lis[i])
print(len(ans) + len(s)//2)

### FIXED CODE ###

from collections import deque
N = int(input())
lis = []
ans = []
lis_append=lis.append
for i in range(N):
    x,l = map(int, input().split(" "))
    lis_append((x+l,x-l))
lis.sort()
lis = deque(lis)
ans.append(lis.popleft())
while lis:
    a = lis.popleft()
    if a[1] >= ans[-1][0]:
        ans.append(a)
print(len(ans))
### BUGGY CODE ###

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


num =0
for i in range(max(l)+1):
    s =0
    u =0
    for j in l:
        if j <i:
            s +=1
        else:
            u +=1
    if s ==u:
        num +=1
print(num)

### FIXED CODE ###

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


m = sorted(l)
if len(m)%2!=0:
    print(0)
else:
    i = len(m)//2 -1
    ans = m[i+1]-m[i]
    print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 9)
    MOD = 10 ** 9 + 7

    from itertools import permutations

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

    INF = 10 ** 9

    G = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        G[i][i] = 0

    for _ in range(M):
        A, B, C = map(int, input().split())
        G[A][B] = C
        G[B][A] = C

    for k in range(N + 1):
        for i in range(N + 1):
            for j in range(N + 1):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

    ans = INF
    for tmp in permutations(R):
        score = 0
        for i in range(r - 1):
            score += G[tmp[i]][tmp[i + 1]]
        ans = min(ans, score)

    print (ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from itertools import permutations

N, M, R = map(int, input().split())
r = list(input().split())
edge = np.array([input().split() for _ in range(M)], dtype = np.int64).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))

lst = floyd_warshall(graph, directed = False)
# print (lst)
def calc(path):
    cost = 0
    s = int(path[0]) - 1
    for i in range(1, R):
        g = int(path[i]) - 1
        cost += lst[s, g]
        s = g
    return cost

ans = 10 ** 18
for tmp in permutations(r):
    # print (tmp)
    ans = min(ans, calc(tmp))

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

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),skiprows=1);c=0;l=2**29
while l:h=l;l//=2;b%=h;y=sort(hstack((b-h,b)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=l*2;x,y=a%h,sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-x)-B(y,l-x))%2*l
print(c)
### BUGGY CODE ###

n, k, *p = map(int, open(0).read().split())

p = tuple(p)
max_r = 0
max_i = 0
for i in range(n-k+1):
  r = sum(p[i:i+k])
  
  if r > max_r:
    max_r = r
    max_i = i
    
max_e = 0
for j in range(max_i, max_i+k):
  max_e += (p[j]+1)/2

print(max_e)

### FIXED CODE ###

n, k, *p = map(int, open(0).read().split())

q = []
for p_i in p:
  q.append((p_i+1)/2)
  
s = [0]
pre_s = 0
for q_i in q:
  pre_s += q_i
  s.append(pre_s)

ans = 0
for i in range(n-k+1):
  if ans < (s[i+k] - s[i]):
    ans = s[i+k] - s[i]
    
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

PY_list = defaultdict(list)
for i in range(len(PY)):
    PY_list[PY[i][0]].append([i, PY[i][1]])
#print(PY_list)

for pyl in PY_list.values():
    #print(pyl)
    pyl.sort(key = lambda x: x[1])
#print(N, M, PY)
#print(PY_list)
#print(PY[0][0])
for i in range(len(PY)):
    n = PY_list[PY[i][0]].index([i, PY[i][1]])
    print("{:06d}{:06d}".format(PY[i][0], n + 1))

### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(M)]

PY_list = defaultdict(list)
for i in range(len(PY)):
    PY_list[PY[i][0]].append([i, PY[i][1]])
#print(PY_list)

py_opt = dict()
for pyl in PY_list.values():
    pyl.sort(key = lambda x: x[1])
    for i in range(len(pyl)):
        #print(i)
        py_opt[pyl[i][0]] = i

#print(py_opt)
#print(PY_list)
for i in range(len(PY)):
    #n = PY_list[PY[i][0]].index([i, PY[i][1]])
    n = py_opt[i]
    print("{:06d}{:06d}".format(PY[i][0], n + 1))
### BUGGY CODE ###

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

def maximum(list):
    sub = []
    for i,x in enumerate(list):
        if sub == [] or x > sub[0]:
            sub = [x,i]
    return sub[0],sub[1]

for i in range(m):
    x,idx = maximum(a_list)
    a_list[idx] = x//2

print(sum(a_list))

### FIXED CODE ###

import heapq

# O(MlogN)
n,m = map(int,input().split())
a_list = list(map(lambda x: int(x)*(-1),input().split()))
heapq.heapify(a_list)

for _ in range(m):
    tmp_min = heapq.heappop(a_list)
    heapq.heappush(a_list, (-1)*(-tmp_min//2)) 

print(-sum(a_list))
### BUGGY CODE ###

import collections

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
c = collections.Counter(A)

if (K - Q) > 0:
    for _ in range(N):
        print('Yes')
else:
    l = []
    for i,v in dict(c).items():
        if v >(Q - K):
            l.append(i-1)
    l.sort()
    for j in range(N):
        if j in l:
            print('Yes')
            l.pop(0)
            if l == []:
                for _ in range(N-j-1):
                    print('No')
                break
        else:
            print('No')

### FIXED CODE ###

import collections

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
c = collections.Counter(A)

if (K - Q) > 0:
    for _ in range(N):
        print('Yes')
else:
    l = ['No'] * N
    for i,v in dict(c).items():
        if v >(Q - K):
            l[i-1] = 'Yes'
    for j in l:
        print(j)
### BUGGY CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

costs = []
links = []
for i in range(n):
    costs.append([0] * i)
    links.append(set())

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1

    for j in range(l, r):
        for k in range(j + 1, r + 1):
            c0 = costs[k][j]
            if c0 == 0 or c0 > c:
                costs[k][j] = c
                links[k].add(j)

h = []
heapq.heappush(h, (0, n-1))

while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if n0 == 0:
        print(c0)
        exit()

    for n1 in links[n0]:
        c1 = costs[n0][n1]
        heapq.heappush(h, (c0 + c1, n1))

print("-1")



### FIXED CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

links = []
for i in range(n):
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if (closed & (1 << n0)) != 0:
        continue
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n2))

print("-1")
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline

def main():
    R, C, K = map(int, input().split())

    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    cell = np.full((R+1, C+1), 0, dtype=np.int64)

    for i in range(K):
        x, y, c = map(int, input().split())
        cell[x-1][y-1] = c

    dp[0][1][0] = dp[1][0][0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

    print(dp[R][C][3])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np
from numba import jit, void, i8
input = sys.stdin.readline

def main():
    R, C, K = map(int, input().split())

    L_INF = int(1e17)
    dp = np.full((R+1, C+1, 4), -L_INF, dtype=np.int64)
    cell = np.full((R+1, C+1), 0, dtype=np.int64)

    for i in range(K):
        x, y, c = map(int, input().split())
        cell[x-1][y-1] = c

    f(dp, cell, R, C)

    print(dp[R][C][3])

@jit(void(i8[:,:,:],i8[:,:],i8,i8))
def f(dp, cell, R, C):
    dp[0][1][0] = dp[1][0][0] = 0
    for i in range(1, R + 1):
        for j in range(1, C + 1):
            for k in range(4):
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j][k-1])
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
                if k > 0:
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + cell[i-1][j-1])
                if k == 1:
                    dp[i][j][k] = max(dp[i][j][1], dp[i-1][j][3] + cell[i-1][j-1])

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

n , m = map(int, input().split())
a = list(map(int,input().split()))
for i in range(m):
    b , c = map(int, input().split())
    a+=[c]*b
a.sort(reverse=True)
a=a[:n]
print(sum(a))


### FIXED CODE ###

n , m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()
bc=[]
for i in range(m):
    b , c = map(int, input().split())
    bc.append((b,c))
bc.sort(key = lambda x : x[1],reverse=True)

t=0
for i in range(m):
    b,c=bc[i]
    if t>=n:
        break
    if a[t]>=c:
        break
    for j in range(b):
        if a[t]<c:
            a[t]=c
            if t<n-1:
                t+=1
        else:
            break
print(sum(a))
### BUGGY CODE ###

from sys import stdin
from itertools import takewhile

n = int(stdin.readline().rstrip())
s = [1, 1]
for i in range(2, n+1):
    s.append(i*s[i-2])

s_r = list(reversed(str(s[-1])))
zeros = list(takewhile(lambda x: x == "0", s_r))
print(len(zeros))

### FIXED CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
count = 0
a = n//2
b = 5

if n % 2 != 0:
    print(count)
else:
    while True:
        count += a//b
        if a//b == 0:
            break
        b *= 5

    print(count)
### BUGGY CODE ###

import sys
n = int(input())
an = list(map(int, sys.stdin.readline().rstrip().split()))
q = int(input())

import numpy as np
from collections import deque

sum = np.sum(an)
ans = deque()

for _ in range(q):
    b,c = map(int, input().split())
    for i in range(n):
        if b == an[i]:
            an[i]=c
            sum += c-b
    ans.append(sum)

while ans:
    print(ans.popleft())

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
li = [0]*100001
for a in A:
    li[a] += 1
ans = sum(A)
# print(dict_A)
for i in range(Q):
    b, c = map(int, input().split())
    ans += (c-b)*li[b]
    li[c] += li[b]
    li[b] = 0
    print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())

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

d = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    if i != n-1:
        d[i][i] =0.5
        d[i][i+1]=0.5
    else:
        d[i][0] = 0.5
        d[i][i] = 0.5

d = np.array(d)

ans = np.dot(np.linalg.inv(d), A.T)
ans = np.array(ans, dtype="int")
ans = (ans.T).tolist()

print(' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0 for _ in range(n)]
total_rain = sum(a)
tmp = total_rain

#一つ飛ばしで合計から引いていく。
#X1 = S − (X2 + ... + XN ) = S − 2(A2 + A4 + ... + AN−1)がtmp
for r in a[:-1:2]:
  tmp -= r*2
  

#tmp=XN+1なのでX1も漸化式から計算
ans[-1] = tmp
ans[0] = a[-1] * 2 - tmp

tmp = ans[0]
#Xi+1 = 2Ai − Xi で他を求める
#i=n-1の時に最後もちゃんと更新される
for i in range(1, n-1):
    ans[i] = 2 * a[i-1] - ans[i-1]

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

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

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
MIN = n+1
count = 0
for i in range(n):
    if MIN > p[i]:
        count += 1
    MIN = min(MIN,p[i])
print(count)
### BUGGY CODE ###

s,t=list(input()),list(input())
n=len(s)
m=len(t)
ss=[0]*n
tt=[0]*n
for i in range(n):
  ss[i]=s.count(s[i])
for i in range(m):
  tt[i]=t.count(t[i])
if ss==tt:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import sys
s0,t0=input(),input()
s,t=list(s0),list(t0)
n=len(s)
sn=set(s)
tn=set(t)
if len(sn)!=len(tn) or len(s)!=len(t):
  print('No')
  sys.exit()
for i in range(n):
  if s[i]!=t[i]:
    if s.index(s[i])!=t.index(t[i]):
      print('No')
      sys.exit()
print('Yes')
### BUGGY CODE ###

from collections import Counter
N=int(input())
count=0
s=[]
for i in range(N):
    s.append(input())
for t in range(N):
    for i in range(N):
        if t>=i:
            continue
        if Counter(s[t])==Counter(s[i]):
            count+=1
        if i==t:
            count-=1
print(int((count)))

### FIXED CODE ###

N=int(input())
S=[''.join(sorted((input()))) for i in range(N)]
P={}
for i in range(N):
    if S[i] in P:
        P[S[i]]+=1
    else:
        P[S[i]]=0
for i in P.keys():
    if P[i]>=2:
        P[i]=P[i]*(P[i]+1)/2
print(int(sum(P.values())))
### BUGGY CODE ###

S = input()
 
N = len(S)
 
cnt = 0
alr = []
for i in range(N-4):
    if not i in alr:
        cnt_i = 1
        for j in range(i+4,N):
            S_int = int(S[i:(j+1)])
            if S_int % 2019 == 0:
                cnt += cnt_i
                cnt_i += 1
                alr.append(j+1)
print(cnt)
        


### FIXED CODE ###

S = input()
 
N = len(S)

mod = 2019
d = [0 for i in range(2019)]
d[0] = 1
t = 1
rem = 0

for i in reversed(S):
    rem += int(i) * t
    rem %= mod
    t *= 10
    t %= mod
    d[rem] += 1

print(int(sum([i * (i-1) / 2 for i in d])))
### BUGGY CODE ###

import sys
N = int(input())
L = [i for i in map(int, input().split())]
ans = 0

L.sort()
#print(L)
if N == 3:
    if L[0] + L[1] > L[2]:
        print("1")
        sys.exit()

for i in range(len(L)-2):
    for j in range(i+1,len(L)-1):
        for k in range(j+1,len(L)):
            if L[i] + L[j] > L[k]:
                ans += 1
                #print(L[i], L[j], L[k])
            else:
                #print("break")
                break
print(ans)

### FIXED CODE ###

import sys
import bisect
N = int(input())
L = [i for i in map(int, input().split())]
ans = 0

L.sort()
#print(L)
if N == 3:
    if L[0] + L[1] > L[2]:
        print("1")
        sys.exit()

for i in range(len(L)-2):
    for j in range(i+1,len(L)-1):
        index = bisect.bisect_left(L,L[i]+L[j],j+1)
        #print(index)
        ans += (index - 1) - (j + 1) + 1
print(ans)
### BUGGY CODE ###

N = int(input())
mojiretu = [input() for _ in range(N)]
mojiretu2 = []
answer = 0

for n in mojiretu:
  mojiretu2.append(sorted(list(n)))
 
for index, moji in enumerate(mojiretu2):
  i = index+1
  while i < N:
    if moji == mojiretu2[i]:
      answer+=1
    i+=1

print(answer)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
from itertools import groupby

def solve(N: int, s: "List[str]"):
    s = [sorted(s[i]) for i in range(N)]
    s.sort()
    group = groupby(s)
    answer = 0
    for key, group in group:
        a = len(list(group))
        answer += int(a*(a-1)/2) if a > 1 else 0
    print(answer)
   


    # for i in range(N):
    #     a = 1
    #     pop_index = []
    #     for j in range(i+1,len(ss)):
    #         if ss[i] == ss[j]:
    #             a += 1
    #             pop_index.append(j)
        
    #     ss = [ss[i] for i in range(len(ss)) if i not in pop_index]
    #     answer += int(a*(a-1)/2) if a > 1 else 0
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)

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

# coding: utf-8
N,M=map(int,input().split())
A=[0]*M
for i in range(M):
    A[i]=int(input())
#print(A)
def dp(n):
    dp=[0]*(N+1)
    dp[0]=1
    dp[1]=0 if 1 in A else 1
    for i in range(N-1):
        if (i+2) in A:
            dp[i+2]=0
        else:
            dp[i+2]=dp[i+1]+dp[i]
    return dp[n]
print(dp(N)%(10**9+7))

### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
A=[0]*M
dp=[-1]*(N+1)
for i in range(M):
    tmp=int(input())
    dp[tmp]=0
#print(dp)
dp[0]=1
dp[1]=0 if dp[1]==0 else 1

for i in range(2,N+1):
    if dp[i]!=0:
        dp[i]=dp[i-1]+dp[i-2]
        
print(dp[N]%(10**9+7))
### BUGGY CODE ###


import sys
input = sys.stdin.readline
import numpy as np

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [1 if (s[i]=="A" and s[i+1] =="C") else 0 for i in range(n-1)]
    a = np.array(a)
    for i in range(q):
        print(np.sum(a[lr[i][0]-1:lr[i][1]-1]))

question()


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
import bisect
left = bisect.bisect_left
right = bisect.bisect_right

def question():
    n, q = list(map(int, input().split()))
    s = input()
    lr = [list(map(int, input().split())) for i in range(q)]
    a = [i for i in range(n-1) if s[i:i+2]=="AC"]

    for i in range(q):
        left_index = left(a, lr[i][0]-1)
        right_index = right(a, lr[i][1]-2)
        print(right_index - left_index)

question()
### BUGGY CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 150000,200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,750000,720000,800000,825000,850000,875000,900000,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 1810893, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,9821778,10261678,10997400,11366472,11736253,12106789,12478098,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])


### FIXED CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 150000,200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,700000,720000,750000,800000,825000,850000,875000,900000,912500,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 1810893, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,9529244,9821778,10261678,10997400,11366472,11736253,12106789,12478098,12664043,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])
### BUGGY CODE ###

N,W = map(int,input().split())
Value = []
weight = []
inf=float("inf")
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1): dp[0][i]=0

for i in range(N):
    w,v = map(int,input().split())
    Value.append(v)
    weight.append(w)


for i in range(N):
  for w in range(W+1):
    if w>=weight[i]:
      dp[i+1][w] = max(dp[i][w-weight[i]]+Value[i],dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]

print(dp[N][W])

### FIXED CODE ###

N,W = map(int,input().split())
Value = []
weight = []
inf=float("inf")
dp=[[-inf for i in range(W+1)] for j in range(N+1)]
for i in range(W+1): dp[0][i]=0

for i in range(N):
    w,v = map(int,input().split())
    Value.append(v)
    weight.append(w)


for i in range(N):
  for w in range(W+1):
    if w>=weight[i]:
      dp[i+1][w] = max(dp[i][w-weight[i]]+Value[i],dp[i][w])
    else:
      dp[i+1][w] = dp[i][w]

print(dp[N][W])