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

n = int(input())
a = [int(input()) for i in range(n)]
b = [-1]*n
for i in range(n):
    b[i] = max(a[:i]+a[i+1:])
for key in b:
    print(key)

### FIXED CODE ###

import numpy as np
n = int(input())
a = [int(input()) for i in range(n)]
max = np.max(a)
max_pos = np.argmax(a)
b = [max]*n
b[max_pos] = np.max(a[:max_pos]+a[max_pos+1:])
for key in b:
    print(key)
### BUGGY CODE ###

def main():
  e,M=enumerate,10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[0]*(k+1)for _ in range(n+1)]
  dp[0][0]=1
  for b,d,a in zip(dp,dp[1:],a):
    a+=1
    t=0
    for j,v in e(b[:a]):
      t+=v
      t%=M
      d[j]=t
    for j,(w,v)in e(zip(b,b[a:]),a):
      t+=v-w
      t%=M
      d[j]=t
  print(t)
main()

### FIXED CODE ###

def main():
  e,M=enumerate,10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[0]*(k+1)for _ in range(n+1)]
  dp[0][0]=1
  for i,(b,d,a)in e(zip(dp,dp[1:],a),1):
    t=0
    for j,v in e(b):
      t+=v
      if j>a:t-=b[~a+j]
      t%=M
      d[j]=t
  print(t)
main()
### BUGGY CODE ###

N, M = list(map(int, input().split()))
readline = []
ACs = []
ans1 = 0
ans2 = 0

for i in range (M):
    readline.append(input().split())
    x = readline[i][0]

    if (readline[i][1] == 'AC' and ACs.count(x) == 0):
        ACs.append(x)
        ans1 += 1
        for j in range (i):
            if (readline[j][0] == x):
                ans2 += 1

print(str(ans1) + ' ' + str(ans2))

### FIXED CODE ###

from sys import stdin
n,m = map(int,stdin.readline().split())
prob = dict()
AC,WA = 0,0
for _ in range(m):
	p,s = stdin.readline().split()
	p = int(p)
	if p in prob:
		if s == "AC":
			if prob[p] > 0:
				AC += 1
				WA += prob[p]
				prob[p] = 0
		else:
			if prob[p] > 0: prob[p] += 1
	else:
		if s == "AC":
			prob[p] = 0
			AC += 1
		else:
			prob[p] = 1
print(AC,WA)
### BUGGY CODE ###

a, b, x = map(int,input().split())
N = 0
for i in range(a, b+1):
    if i % x == 0:
        N = N + 1
print(N)

### FIXED CODE ###

a, b, x = map(int,input().split())
N = 0
if a%x ==0:
    N = int((b-a)//x)+1
else:
    c = a + (x-a%x)
    if b>=c:
        N = int((b-c)//x)+1
print(N)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
d = []
for _ in range(m):
  b,c = map(int,input().split())
  d.extend([c]*b)
d.sort(reverse =True)
d_big = d[:n]


a += d_big
a.sort(reverse = True)
print(sum(a[:n]))
  

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = [tuple(map(int,input().split())) for _ in range(m)]

bc.sort(key = lambda x: x[1],reverse = True)
i = 0
j = 0
ad = []
while i < n and j < m:
    ad.extend([bc[j][1]]*bc[j][0])
    i += bc[j][0]
    j += 1
    
if len(ad) < n:
    ad.extend([0]*(n-len(ad)))

a.sort(reverse = True)

i = 0
j = 0
k = 0
ans = 0
while k < n :
    if a[i] > ad[j]:
        ans += a[i]
        i += 1
        k += 1
    else:
        ans += ad[j]
        j += 1
        k += 1
  
print(ans)
### BUGGY CODE ###

N = int(input())
H = list(map(int,input().split()))
kekka = 'Yes'
if N != 1:
    for i in range(1,N):
        if max(H[0:i]) - 1 > H[i]:
            kekka = 'No'
print(kekka)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
kekka='Yes'
maxx = 0
for i in range(N):
    if H[i] < maxx -1:
        kekka = 'No'
        break
    else:
        maxx = max(H[i],maxx)
print(kekka)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    prev_A = False
    for j in range(l - 1, r):
        if S[j] == 'A':
            prev_A = True
        elif prev_A == True and S[j] == 'C':
            cnt += 1
            prev_A = False
        else:
            prev_A = False
    print(cnt)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

c = [0]
for j in range(1, N):
    if S[j - 1] == 'A' and S[j] == 'C':
        c.append(c[-1] + 1)
    else:
        c.append(c[-1])

# 0 1 1 1 2 2 3
# A C A A C A C
# 1 2 3 4 5 6 7
for i in range(Q):
    l, r = map(int, input().split())
    print(c[r - 1] - c[l - 1])
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
I = [list(map(int,input().split())) for i in range(q)]
AC = []
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        AC += [i]
for i in range(q):
    AC_q = [j for j in AC if I[i][0]-1 <= j <= I[i][1]-2]
    print(len(AC_q))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
I = [list(map(int,input().split())) for i in range(q)]
AC = []
ac = 0
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ac += 1
        AC += [ac]
    else:
        AC += [ac]
AC = [0] + AC + [ac]
for i in range(q):
    ac_q =  AC[I[i][1]-1]-AC[I[i][0]-1]
    print(ac_q)
### BUGGY CODE ###

n=int(input())
lis=list(map(int,input().split()))
num=(n*(n+1))//2
if sum(lis)%num!=0:
  print("NO")
  exit()
ans=0
for i in range(n):
  if abs(lis[i]-lis[i-1]-sum(lis)//num)%n!=0:
    print("NO")
    exit()
  ans+=abs(lis[i]-lis[i-1]-sum(lis)//num)//n
if ans == sum(lis)//num:print("YES")
else:print("NO")


### FIXED CODE ###

n=int(input())
lis=list(map(int,input().split()))
num=(n*(n+1))//2
ll=sum(lis)
if ll%num!=0:
  print("NO")
  exit()
ans=0
for i in range(n):
  if abs(lis[i]-lis[i-1]-ll//num)%n!=0:
    print("NO")
    exit()
  ans+=abs(lis[i]-lis[i-1]-ll//num)//n
if ans == ll//num:print("YES")
else:print("NO")
### BUGGY CODE ###

N = int(input())
S = input()
sum = 0
for i in range(N):
    for j in range(i):
        for k in range(j):
            if(k - j == j - i):
                continue
            if(S[i] == S[j]):
                continue
            elif(S[j] == S[k]):
                continue
            elif(S[i] == S[k]):
                continue
            sum += 1
            
print(sum)

### FIXED CODE ###

N = int(input())
S = input()


R = []
B = []
G = []
p = 0
for i in S:
    if(i == "R"):
        R.append(p)
    elif(i == "B"):
        B.append(p)
    elif(i == "G"):
        G.append(p)
    p += 1
R = set(R)
B = set(B)
G = set(G)
sum = len(R) * len(B) * len(G)
for r in R:
    for b in B:
        up = max(r, b)
        dw = min(r, b)
        d = up-dw
        if up + d in G:
            sum -= 1
        if dw - d in G:
            sum -= 1
        if (r+b)/2 in G:
            sum -= 1

print(sum)
### BUGGY CODE ###

def resolve():
    N, Q = [int(i) for i in input().split()]
    S = input()
    lr = [list(map(int, input().split())) for _ in range(Q)]
    for l, r in lr:
        print(S.count("AC", l - 1, r))


resolve()


### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    N, Q = [int(i) for i in input().split()]
    S = input()
    pre = [0 for _ in range(N)]
    for i in range(N - 1):
        pre[i + 1] = pre[i] + (1 if S[i:i + 2] == "AC" else 0)
    for _ in range(Q):
        l, r = [int(i) for i in input().split()]
        print(pre[r - 1] - pre[l - 1])


resolve()
### BUGGY CODE ###

from collections import deque
n,q=map(int,input().split())
tree=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a) # 無向グラフなので
ans=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

stack=deque([[0,-1]]) # 根の位置、現位置の元になる根
visited=[0]*n
visited[0]=1

while stack:
    cur,rot=stack[-1]
    for i in tree[cur]:
        if visited[i]==0 and i!=rot:
            visited[i]=1
            ans[i]+=ans[cur]
            stack.append([i,cur])
            break
    else:
        stack.pop()
print(*ans)

### FIXED CODE ###

#「探索候補スタック」「探索済みリスト」「現在地点」の３点セットでとらえる
n,q=map(int,input().split())
mat=[set() for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    mat[a-1].add(b-1)
    mat[b-1].add(a-1) # プラスした要素
count=[0]*n
for _ in range(q):
    p,score=map(int,input().split())
    count[p-1]+=score

stack=[[0,0,-1]]
while stack:
    # print(stack)
    num,cnt,pr=stack.pop()
    count[num]+=cnt
    for k in mat[num]:
        if k==pr:
            continue
        stack.append([k,count[num],num])
print(*count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 100000000000000
for i in range(n-1):
  ans = min(ans,abs(sum(a[:i+1]) - sum(a[i+1:])))
print(ans)
  

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(n-1):
  a[i+1] += a[i]
ans = 100000000000000
for i in range(n-1):
  ans = min(ans, abs(a[-1] - 2*a[i]))

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

import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

for i in range(N):
    a,b = (int(x) for x in input().split())
    AB.append([a,b])

AB = sorted(AB , key = lambda x : x[0])
heap = []
j = 0

for i in range(M+1):
    while j<N and AB[j][0] < i+1:
        heapq.heappush(heap,-AB[j][1])
        j += 1

    if len(heap):
        heapq.heapify(heap)
        sum += -heapq.heappop(heap)
                           
print(sum)
    


### FIXED CODE ###

import heapq

N,M = (int(x) for x in input().split())
AB = []
sum = 0

for i in range(N):
    a,b = (int(x) for x in input().split())
    AB.append([a,b])

AB = sorted(AB , key = lambda x : x[0])
heap = []
j = 0

for i in range(M+1):
    while j<N and AB[j][0] < i+1:
        heapq.heappush(heap,-AB[j][1])
        j += 1

    if len(heap):
        sum += -heapq.heappop(heap)
                           
print(sum)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

INF = 10 ** 5
nums = 401

dp = [[[INF for _ in range(nums+100)] for _ in range(nums+100)] for _ in range(N+1)]

dp[0][0][0] = 0

for i in range(N):
    for sum_a in range(nums):
        for sum_b in range(nums):
            #if dp[i][sum_a][sum_b] == INF:
            #    continue
            dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            dp[i+1][sum_a][sum_b] = min(dp[i+1][sum_a][sum_b], dp[i][sum_a][sum_b])
            #dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            #print(i, dp[i][sum_a][sum_b], sum_a, sum_b)


res = INF
for i in range(1, nums):
    for j in range(1, nums):
        if i * Mb == j * Ma:
            res = min(res, dp[N][i][j])

if res == INF:
    res = -1

print(res)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
a = [0] * N
b = [0] * N
c = [0] * N
for i in range(N):
    a[i], b[i], c[i] = map(int, input().split())

INF = 10 ** 5
nums = 401

dp = [[[INF for _ in range(nums+100)] for _ in range(nums+100)] for _ in range(N+1)]

dp[0][0][0] = 0

for i in range(N):
    for sum_a in range(nums):
        for sum_b in range(nums):
            #if dp[i][sum_a][sum_b] == INF:
            #    continue
            dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            dp[i+1][sum_a][sum_b] = min(dp[i+1][sum_a][sum_b], dp[i][sum_a][sum_b])
            #dp[i+1][sum_a+a[i]][sum_b+b[i]] = min(dp[i+1][sum_a+a[i]][sum_b+b[i]], dp[i][sum_a][sum_b] + c[i])
            #print(i, dp[i][sum_a][sum_b], sum_a, sum_b)


res = INF
for i in range(1, nums):
    for j in range(1, nums):
        if i * Mb == j * Ma:
            res = min(res, dp[N][i][j])

if res == INF:
    res = -1

print(res)
### BUGGY CODE ###

import sys
stdin = sys.stdin
from math import sqrt

def li(): return map(int, stdin.readline().split())

def gcd(A, B):
    if B > A:
        return gcd(B, A)
    while B != 0:
        A, B = B, A - B
    return A

def test_gcd():
    assert gcd(8, 4) == 4


A, B, K = tuple(li())
count = 0
g = gcd(A, B)
can = set()
cnt = 0
for i in range(1, int(sqrt(g)) + 1):
    if g % i == 0:
        cnt += 1
        can.add(i)
        can.add(g // i)
        if cnt >= K:
            break

can = sorted(can, reverse=True)
print(can[K - 1])


### FIXED CODE ###

import sys
stdin = sys.stdin
from math import sqrt

def li(): return map(int, stdin.readline().split())




A, B, K = tuple(li())
count = 0
g = min(A, B)
can = []
cnt = 0
for i in range(1, g + 1):
    if A % i == 0 and B % i == 0:
        
        
        can.append(i)



print(can[-K])
### BUGGY CODE ###

import copy

h, w = map(int, input().split())

acol = ["."]*(h+2)
acol[0] = ["."]*(w+2)
acol[h+1] = ["."]*(w+2)
arow = ["."]*(w)
count = 0
flag = 1

for i in range(h):
    ac = input()

    for j in range(w):
        arow[j] = ac[j]

    acol[i+1] = ["."] + arow + ["."]

while flag != 0:
    flag = 0
    acolaf = copy.deepcopy(acol)

    for i in range(h):

        for j in range(w):

            if acol[i+1][j+1] != "#":
                
                if acol[i+1][j] == "#" or acol[i][j+1] == "#" or acol[i+2][j+1] == "#" or acol[i+1][j+2] == "#":
                    acolaf[i+1][j+1] = "#"
                    flag += 1
        
    if flag > 0:
        count += 1
    
    acol = acolaf
            
print(count)

### FIXED CODE ###

import numpy as np
import copy

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

a = np.array([[0 if (ai[j] == "#") else np.inf for j in range(w)] for ai in a])

for i in range(1, h):
    a[i] = np.minimum(a[i], a[i - 1] + 1)
for i in range(h - 2, -1, -1):
    a[i] = np.minimum(a[i], a[i + 1] + 1)
for i in range(1, w):
    a[:, i] = np.minimum(a[:, i], a[:, i - 1] + 1)
for i in range(w - 2, -1, -1):
    a[:, i] = np.minimum(a[:, i], a[:, i + 1] + 1)

print(int(a.max()))
### BUGGY CODE ###

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

#リストをソート
a=sorted(a)
b=sorted(b)
c=sorted(c)

#二分探索(x以上の最小値index) !同じ物は一個下げる
def lower_bound(arr,x):
    l=0
    r=len(arr)-1#数列arrの最後尾のインデックス
    while l<=r:
        mid=(l+r)//2#中央値検索
        if x==arr[mid]:#ちょうど中央値に存在したとき
            return mid+1
        elif x<arr[mid]:#xが左側の配列に存在するとき
            r=mid-1
        else:#xが右側の配列に存在するとき
            l=mid+1
        #print(mid,r,l)
    return r+1

#二分探索(x以下の最大値)
def upper_bound(arr,x):
    l=0
    r=len(arr)-1#数列arrの最後尾のインデックス
    while l<=r:
        mid=(l+r)//2#中央値検索
        if x==arr[mid]:#ちょうど中央値に存在したとき
            return mid-1
        elif x<arr[mid]:#xが左側の配列に存在するとき
            r=mid-1
        else:#xが右側の配列に存在するとき
            l=mid+1
        #print(mid,r,l)
    return r

#個数をカウント
count=0
for i in range(n):
    if min(a)>=b[i] or max(c)<=b[i]:
        count=0
    else:
        a_count=upper_bound(a,b[i])+1#b要素固定でのa要素の個数
        c_count=lower_bound(c,b[i])+1#b要素固定でのc要素の個数
        count+=a_count*(len(c)-c_count+1)
        #print(upper_bound(a,b[i]),lower_bound(c,b[i]))
        #print(a_count,len(c),c_count,len(c)-c_count+1)
        #print(count)

print(count)


### FIXED CODE ###

# 二分探索
import bisect

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

#リストをソート
a=sorted(a)
b=sorted(b)
c=sorted(c)

count=0
#a[i]の個数
for i in range(n):
    a_count = bisect.bisect_left(a, b[i])
    c_count = bisect.bisect_right(c, b[i])
    count+=a_count*(len(c)-c_count)

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

s=list(input())
ans=0
while True:
    cnt=0
    for i in range(len(s)-1):
        if s[i]=="B" and s[i+1]=="W":
            s[i]="W"
            s[i+1]="B"
            ans+=1
    for j in range(s.count("W")):
        if s[j]=="W":
            cnt+=1
    if cnt==s.count("W"):
        break
print(ans)

### FIXED CODE ###

s=list(input())
ans=0
a=s.count("B")
for i in range(len(s)):
    if s[i]=="B":
        ans+=i
b_cnt=(s.count("W")+(len(s)-1))*s.count("B")//2
print(int(b_cnt-ans))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = [ _ for _ in input()]
lr = [[int(_) for _ in input().split()] for _ in range(Q)]
A = [i for i, _ in enumerate(S, 1) if _ == "A"]
C = [i for i, _ in enumerate(S, 1) if _ == "C"]
AC = [_ for _ in A if _ + 1 in C]
for l,r in lr:
    ans = [_ for _ in AC if l <= _ and _ + 1 <= r]

    print(len(ans))

### FIXED CODE ###

N, Q = map(int, input().split())
S = [ _ for _ in input()]
lr = [[int(_) for _ in input().split()] for _ in range(Q)]
ans = [0] * (N + 1)

for i, data in enumerate(S, 1):
    if data == "A":
        if i >= N:
            break

        if S[i] == "C":
            ans[i] = ans[i - 1] + 1
            continue

    ans[i] = ans[i - 1]

for l, r in lr:
    print(ans[r - 1] - ans[l - 1])
### BUGGY CODE ###

import numpy as np
K = int(input())

def gcd(a,b,c):
  return np.gcd(a,np.gcd(b,c))

sum = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      sum += gcd(i,j,k)
      
print(sum)

### FIXED CODE ###

from math import gcd
K = int(input())
sum = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      sum += gcd(gcd(i,j),k)
      
print(sum)
### BUGGY CODE ###

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


### FIXED CODE ###

N=int(input())
a=list(map(int, input().split()))
c=[0]*(N+2)
for i in range(N-1):
    c[a[i]]+=1
for i in range(1,N+1):
    print(c[i])
### BUGGY CODE ###

N=[int(e) for e in input().split()]
p=[int(e) for e in input().split()]
p2=[0.]*(N[0]-N[1]+1)
for i in range(N[0]-N[1]+1):
    for j in range(N[1]):
        p2[i]=p2[i]+(p[i+j]+1)/2

print(max(p2))

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N-1):
    p[i+1]=p[i+1]+p[i]
max=p[K-1]
if N>K:
    for i in range(1,N-K+1):
        tmp=p[i+K-1]-p[i-1]
        if max < tmp:
            max=tmp
print((max+K)/2.)
### BUGGY CODE ###

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

S=input()
N=len(S)
mod=2019
data=[(int(S[-i-1])*pow(10,i)) for i in range(0,N)]

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))

### FIXED CODE ###

def equalfind(A):#配列中の等しい要素の組をカウント　オーダーはO(NlogN)
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

S=input()
N=len(S)
mod=2019
data=[(int(S[-i-1])*pow(10,i,mod)) for i in range(0,N)]

for i in range(1,N):
    data[i]+=data[i-1]
    data[i]%=mod

data=[0]+data
data.sort()
print(equalfind(data))
### BUGGY CODE ###

N, W = map(int, input().split())
weight, value = [0]*N, [0]*N
for i in range(N):
	weight[i], value[i] = map(int, input().split())


dp=[[0]*(W+1) for _ in range(N+1)]
#初期条件
#dp[0]=0
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[-1][-1])


"""
def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    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]
    
    return dp[N , W]




import numpy as np
N,W = map(int,input().split())
 
dp=np.zeros(W-1, dtype=np.int64)
for _ in range(N):
	w, v = map(int, input().split())



for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
 
answer = dp.max()
print(answer)
"""

### FIXED CODE ###

N, W = map(int, input().split())
weight, value = [0]*N, [0]*N
for i in range(N):
	weight[i], value[i] = map(int, input().split())


dp=[[0]*(W+1) for _ in range(N+1)]
#初期条件
#dp[0]=0
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[-1][-1])


"""
def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    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]
    
    return dp[N , W]




import numpy as np
N,W = map(int,input().split())
 
dp=np.zeros(W-1, dtype=np.int64)
for _ in range(N):
	w, v = map(int, input().split())



for _ in range(N):
    w,v = map(int,input().split())
    np.maximum(dp[w:], dp[:-w] + v, out = dp[w:])
 
answer = dp.max()
print(answer)
"""
### BUGGY CODE ###

h, w = map(int, input().split())
map_list = []
for _ in range(h):
    map_list.append(list(input()))
x_list = [1, 0, -1, 0]
y_list = [0, 1, 0, -1]
ans = 0
q = []
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            q.append([y, x])
black_num = len(q)
while (black_num < (h*w)):
    q_list = []
    for y, x in q:
        for i in range(4):
            new_y = y + y_list[i]
            new_x = x + x_list[i]
            if (new_y >= 0) & (new_y < h) & (new_x >= 0) & (new_x < w):
                if map_list[new_y][new_x] == ".":
                    map_list[new_y][new_x] = "#"
                    black_num += 1
                    q_list.append([new_y, new_x])
    q = q_list.copy()
    ans += 1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
import numpy as np
H,W,D = map(int, raw_input().split())

Ah = np.array([0]*(H*W))
Aw = np.array([0]*(H*W))

# for h in range(H):
#     As = list(map(int, input().split()))
#     for w in range(W):
#         Ah[As[w]-1] = h
#         Aw[As[w]-1] = w

for h in range(H):
    As = np.array(list(map(int, raw_input().split())))
    Aw[As-1] = np.arange(W)
    Ah[As-1] = h

Q = int(raw_input())

def solve(l, r):
    ans = 0
    ah = Ah[l-1:r][::D]
    ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
    aw = Aw[l-1:r][::D]
    ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
    #ans = sum(Ah[l-1:l+D][::D])
    # while l != r:
    #     x,y = A[l-1]
    #     x2,y2 = A[l+D-1]
    #     ans += abs(x-x2) + abs(y-y2)
    #     l += D
    return ans

lrs = []
for q in range(Q):
    L, R = map(int, raw_input().split())
    #print(solve(L, R))
    lrs.append((L,R))

for info in lrs:
    L,R = info
    print(solve(L, R))




### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
H,W,D = map(int, input().split())

# Ah = np.array([0]*(H*W))
# Aw = np.array([0]*(H*W))
A = [0]*(H*W)
for h in range(H):
    As = list(map(int, input().split()))
    for w in range(W):
        A[As[w]-1] = (h,w)
    # Aw[As-1] = np.arange(W)
    # Ah[As-1] = h


Q = int(input())

# def solve(l, r):
#     ans = 0
#     # ah = Ah[l-1:r][::D]
#     # ans += np.sum(np.abs(ah[1:] - ah[0:-1]))
#     # aw = Aw[l-1:r][::D]
#     # ans += np.sum(np.abs(aw[1:] - aw[0:-1]))
#     ans = sum(Ah[l-1:l+D][::D])
#     while l != r:
#         x,y = A[l-1]
#         x2,y2 = A[l+D-1]
#         ans += abs(x-x2) + abs(y-y2)
#         l += D
#     return ans

Ans = [0]*(H*W)
aa = (H*W) // D
bb = (H*W) % D
for dth in range(1,aa+1):
    for d in range(D):
        if dth*D+d >=H*W:
            break
        x,y = A[(dth-1)*D+d]
        x2,y2 = A[dth*D+d]
        ans = abs(x-x2) + abs(y-y2)
        Ans[dth*D+d] = Ans[(dth-1)*D+d] + ans



lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    print(Ans[R-1] - Ans[L-1])
    #lrs.append((L,R))

# for info in lrs:
#     L,R = info
#     print(solve(L, R))