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

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    H,W = LMIIS()
    A = []
    for _ in range(H):
        A.append(input())
    from copy import deepcopy
    blacks = []
    max_d = 0
    for w in range(W):
        for h in range(H):
            if A[h][w] == '#':
                blacks.append((h,w))
    for w in range(W):
        for h in range(H):
            if A[h][w] == '.':
                d = 10**7
                for i,j in blacks:
                    d = min(d,abs(i-h)+abs(j-w))
                max_d = max(max_d,d)
    print(max_d)


if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    H,W = LMIIS()
    A = []
    for _ in range(H):
        A.append(input())
    from copy import deepcopy
    blacks = deque()
    visited = [[False]*W for _ in range(H)]
    for w in range(W):
        for h in range(H):
            if A[h][w] == '#':
                blacks.append((h,w))
                visited[h][w] = True

    count = -1
    
    while len(blacks) > 0:
        count += 1
        next_blacks = deque()
        while len(blacks) > 0:
            i,j = blacks.pop()
            if 0 <= i-1 and not visited[i-1][j]:
                next_blacks.append((i-1,j))
                visited[i-1][j] = True
            if 0 <= j-1 and not visited[i][j-1]:
                next_blacks.append((i,j-1))
                visited[i][j-1] = True
            if i+1 < H and not visited[i+1][j]:
                next_blacks.append((i+1,j))
                visited[i+1][j] = True
            if j+1 < W and not visited[i][j+1]:
                next_blacks.append((i,j+1))
                visited[i][j+1] = True
        blacks = next_blacks
    print(count)



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

k=int(input())
flag=1
ans=1
r=7%k
p=r
while flag!=0:
    if r%k==0:
        flag=0
    else:
        ans+=1
        p=(p*10)%k
        r+=p
print(ans)


### FIXED CODE ###

k=int(input())
flag=1
ans=1
r=7%k
p=r
if k%2==0:
    print(-1)
    exit()
if k%5==0:
    print(-1)
    exit()
while flag!=0:
    if r%k==0:
        flag=0
    else:
        ans+=1
        p=(p*10)%k
        r+=p
print(ans)
### BUGGY CODE ###

def solve():
    n = int(input())
    dp = [[False]*(n+1)]
    dp[0][0] = True
    way = [1] + [6**i for i in range(1,9) if 6**i <= n] + [9**i for i in range(1,7) if 9**i <= n]
    while True:
        newline = [False] * (n+1)
        for w in way:
            for i in range(0, n+1):
                if i - w < 0: continue
                if newline[i]: continue
                if dp[len(dp)-1][i-w]: newline[i] = True
                if newline[n]: return len(dp)
        dp.append(newline)

print(solve())

### FIXED CODE ###

def solve():
    n = int(input())
    dp = [True] + [False]*(n+1)
    way = [1] + [6**i for i in range(1,9) if 6**i <= n] + [9**i for i in range(1,7) if 9**i <= n]
    loop_counter = 0
    while True:
        loop_counter += 1
        newdp = [False] * (n+1)
        for w in way:
            for i in range(w, n+1):
                if newdp[i]: continue
                if dp[i-w]: newdp[i] = True
                if newdp[n]: 
                    return loop_counter
        dp = [x for x in newdp]

print(solve())
### BUGGY CODE ###

H, W = map(int, input().split())
maze = [0] * H
for i in range(H):
  maze[i] = str(input())

ans = 0  
for i in range(H):#20
  for j in range(W):#20
    if maze[i][j] != "#":
      visited = [[float("inf")] * W for _ in range(H)]
      visited[i][j] = 0
      queue = [[i, j]]
      while queue:#400
        x, y = queue.pop()
        for p, q in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
          if (0 <= x + p < H) and (0 <= y + q < W):
            if (maze[x+p][y+q] !="#"):       
              if visited[x+p][y+q] > visited[x][y] + 1:
                queue.append([x+p, y+q])
                visited[x+p][y+q] = visited[x][y] + 1
      #print(visited)        
      now = 0
      for k in range(H):
        for k2 in range(W):
          if visited[k][k2] < 10 ** 10:
            now = max(now, visited[k][k2])
      ans = max(ans, now)
      
print(ans)

            
            
            
            
        


### FIXED CODE ###

H, W = map(int, input().split())
maze = [0] * H
for i in range(H):
  maze[i] = str(input())

ans = 0  
for i in range(H):#20
  for j in range(W):#20
    if maze[i][j] != "#":
      visited = [[float("inf")] * W for _ in range(H)]
      visited[i][j] = 0
      queue = [[i, j]]
      while queue:#400
        x, y = queue.pop()
        for p, q in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
          if (0 <= x + p < H) and (0 <= y + q < W):
            if (maze[x+p][y+q] !="#"):       
              if visited[x+p][y+q] > visited[x][y] + 1:
                queue.append([x+p, y+q])
                visited[x+p][y+q] = visited[x][y] + 1
      #print(visited)        
      now = 0
      for k in range(H):
        for k2 in range(W):
          if visited[k][k2] < 10 ** 10:
            now = max(now, visited[k][k2])
      ans = max(ans, now)
      
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a_input = list(map(int,input().split()))

a_count = Counter(a_input)
for i in range(n):
    li = [v-1 if k==a_input[i] else v for k,v in a_count.items()]
    len_li = len(li)
    tmp=0
    for l in li:
        tmp+=l*(l-1)//2
    print(tmp)  

### FIXED CODE ###

from collections import Counter
n = int(input())
a_input = list(map(int,input().split()))

a_count = Counter(a_input)

score_dic={}
exclude_dic={}

for k,v in a_count.items():
    score_dic[k]=v*(v-1)//2
    exclude_dic[k]=(v-1)*(v-2)//2

score_sum = sum(score_dic.values())

for i in range(n):
    print(score_sum-score_dic[a_input[i]]+exclude_dic[a_input[i]])
### BUGGY CODE ###

L,R = [int(i) for i in input().split()]

tmp = 2019
ans = 2019

for i in range(L,R):
  for j in range(i+1,R+1):
    tmp = (i*j)%2019
    ans = min(tmp,ans)

print(ans)

### FIXED CODE ###

L,R = [int(i) for i in input().split()]

tmp = 2019
ans = 2019

for i in range(L,R):
  for j in range(i+1,R+1):
    tmp = (i*j)%2019
    ans = min(tmp,ans)
    if ans == 0:
      break
  else:
    continue
  break

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

import sys
sys.setrecursionlimit(10**6)
MOD = 1000000007

k = int(input())
number = 9

ans = 0
for i in range(10,10**7):
    check = 'OK'
    l = len(str(i))
    keta = list(str(i))
    for j in range(l-1):
        if abs(int(keta[j]) - int(keta[j+1])) <= 1:
            pass
        else:
            check = 'NG'
    if check == 'OK':
        number += 1
        if number == k:
            ans = i%MOD
            break
if k <= 9:
    print(k)
else:
    print(ans%MOD)


### FIXED CODE ###

k = int(input())
ans = [i for i in range(1,10)]

i = 0

for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])
### BUGGY CODE ###

import sys,gc

class Deque:
    class Cell2:
        def __init__(self, x, y = None, z = None):
            self.data = x
            self.next = y
            self.prev = z

    def __init__(self):
        head = Deque.Cell2(None)
        head.next = head        
        head.prev = head
        self.size = 0
        self.head = head

    def push_front(self, x):
        h = self.head
        q = h.next
        p = Deque.Cell2(x, q, h)
        h.next = p
        q.prev = p
        self.size += 1

    def pop_back(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.prev
        p = q.prev
        p.next = h
        h.prev = p
        self.size -= 1
        return q.data

    def pop_front(self):
        if self.size == 0: raise IndexError
        h = self.head
        q = h.next
        p = q.next
        p.prev = h
        h.next = p
        self.size -= 1
        return q.data

    def delete(self,x):
        h=self.head.next
        while h.data!=x:
            h=h.next
            if h==self.head: return
        q=h.next
        p=h.prev
        q.prev=p
        p.next=q
        self.size -= 1
        return

    def __str__(self):
        if self.size == 0: return
        buff = ''
        n = self.size
        cp = self.head.next
        while n > 1:
            buff += '%s ' % cp.data
            cp = cp.next
            n -= 1
        buff += '%s' % cp.data
        return buff
    
A=Deque()
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.push_front(int(s[1]))
    elif s[0] == 'delete':
        A.delete(int(s[1]))
    elif s[0] == 'deleteFirst':
        A.pop_front()
    elif s[0] == 'deleteLast':
        A.pop_back()
    n -=1
    
print A

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

N = int(input())
x = [0] * N
y = [0] * N

for i, A in enumerate(input().split()):
  x[i] = int(A)
  
for i in range(N):
  for j in range(N):
    index = (i + j) % N
    y[i] += ((-1) ** j) *  x[index]
    
str_y = map(str, y)
output = " ".join(str_y)
print(output)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
y = [0] * N

odd = sum([n for i, n in enumerate(x) if i % 2 == 1])
even = sum([n for i, n in enumerate(x) if i % 2 == 0])
y[0] = even - odd

for i in range(N-1):
  y[i+1] = 2 * x[i] - y[i]


str_y = map(str, y)
output = " ".join(str_y)
print(output)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

cost = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
cd = {}
for a in A:
    if cost[a] in cd:
        cd[cost[a]] = max(cd[cost[a]], a)
    else:
        cd[cost[a]] = a

dp = [(0, [])]
for i in range(1, N + 1):
    mx, mxl, mxs = int(-1e10), [], ""
    for c in cd:
        if i - c >= 0 and mx <= dp[i - c][0] + 1 and 0 <= dp[i - c][0] and mxs <= ''.join(map(str, sorted(dp[i - c][1], reverse=True))):
            mx, mxl = dp[i - c][0] + 1, dp[i - c][1] + [cd[c]]
            mxs = ''.join(map(str, sorted(dp[i - c][1], reverse=True)))
    dp.append((mx, mxl))

ans = dp[-1][1]
print(''.join(map(str, sorted(ans, reverse=True))))


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

dp = [0] + [-1] * N
for i in range(1, N + 1):
    for a, c in cd:
        if i - c >= 0 and 0 <= dp[i - c]:
            dp[i] = max(dp[i], dp[i - c] + 1)

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if i - c >= 0 and dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

print(''.join(map(str, ans)))
### BUGGY CODE ###

n, k = map(int, input().split())
s = input() + "2"

c = []
ci = 1
for i in range(n):
  if s[i] == s[i+1]:
    ci += 1
  else:
    c.append(ci)
    ci = 1

c = c + [0]
ans = 1

if s[0] == "1":
  for i in range(0, len(c), 2):
    if i+2*k+1 > len(c):
      ans = max(ans, sum(c[i:]))
    else:
      ans = max(ans, sum(c[i:i+2*k+1]))
else:
  c = [0] + c
  for i in range(0, len(c), 2):
    if i+2*k+1 > len(c):
      ans = max(ans, sum(c[i:]))
    else:
      ans = max(ans, sum(c[i:i+2*k+1]))

print(ans)

### FIXED CODE ###

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

c = [0]
import itertools
for _, g in itertools.groupby(s):
  c.append(c[-1] + len(list(g)))
  
c = c[1:]
if s[0] == "1":
  c = [0] + c
else:
  c = [0,0] + c
if s[-1] == "0":
  c = c + [c[-1]]

ans = 0
for i in range(0,len(c), 2):
  end = min(i+2*k+1, len(c)-1)
  ans = max(ans, c[end]-c[i])

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

n,a,b=map(int,input().split())
sum=0
while n>sum:
    sum+=(a+b)
x=sum//(a+b)-1
left=n-x*(a+b)
if left<=a:
    print(a*x+left)
else:
    print(a*x+a)

### FIXED CODE ###

n,a,b=map(int,input().split())
x=n//(a+b)
left=n-x*(a+b)
if left<=a:
    print(a*x+left)
else:
    print(a*x+a)
### BUGGY CODE ###

## DP問題

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

match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}


ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())

dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"

for i in range(N+1):
    for a,k in zip(ns,ks):
        if i+k <= N:
            dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))
        else:
            continue
print(dp[N])


### FIXED CODE ###

## DP問題
 
N,M = map(int,input().split())
As = list(map(str,input().split()))
match = {"1":2, "2":5, "3":5,
         "4":4, "5":5, "6":6,
         "7":3, "8":7, "9":6}
 
# test
# N, M = 10000, 9
# As = [str(i) for i in range(1,10)]
 
 
ws = {} #マッチの数に対しての、作れる数字の最大値を算出
for a in As:
    w = match[a] #数aに使うマッチの数
    try: 
        ws[str(w)] = max(a,ws[str(w)])
    except:
        ws[str(w)] = a
ks = list(map(int,ws.keys()))
ns = list(ws.values())
 
dp = ["0" for _ in range(N+1)]
for i in range(1,min(ks)):#最小
    dp[i] = "-1"
 
for i in range(N+1):
    # print(i)
    for a,k in zip(ns,ks):
        if i+k <= N:
            if dp[i] == "-1":
                dp[i+k] = str(max(int(dp[i]+a),int(dp[i+k])))
            elif dp[i] == "0":
                dp[i+k] = str(max(int(a),int(dp[i+k])))
            elif len(dp[i+k]) < len(dp[i])+1:
                    dp[i+k] = dp[i]+a
            elif len(dp[i+k]) == len(dp[i])+1:
                dp[i+k] = max(dp[i+k],dp[i]+a)
            else:
                dp[i+k] = str(max(int(dp[i+k]),int(dp[i]+a)))

        else:
            continue
print(dp[N])
### BUGGY CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sumval += math.gcd(math.gcd(a,b),c)
print(sumval)

### FIXED CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        f = math.gcd(a,b)
        for c in range(1, K+1):
            g = math.gcd(f,c)
            sumval += g
print(sumval)
### BUGGY CODE ###

import heapq
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort(reverse=True)
heapq.heapify(x)
ans=0
for i in range(m):
    y=heapq.nlargest(1,x)[0]
    x.remove(y)
    x.append(y//2)
for j in range(n):
    ans+=x[j]
print(ans)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
x=list(map(int,input().split()))
for k in range(n):
    x[k]-=2*x[k]
heapq.heapify(x)
ans=0
for i in range(m):
    maxvalue=heapq.heappop(x)*(-1)
    heapq.heappush(x,(maxvalue//2)*(-1))
ans=-1*sum(x)
print(ans)
### BUGGY CODE ###

#


def main():
    n = int(input())
    a = [int(s) for s in input().split(" ")]
    counts = {}
    for i in a:
        if i in counts:
            counts[i] += 1
        else:
            counts[i] = 1
    results = {}
    for i in a:
        if i in results:
            print(results[i])
            continue
        count = 0
        for k, v in counts.items():
            if k == i:
                v -= 1
            if v > 1:
                count += (v * (v - 1) // 2)
        print(count)
        results[i] = count


if __name__ == '__main__':
    main()


### FIXED CODE ###

#


def main():
    n = int(input())
    a = [int(s) for s in input().split(" ")]
    counts = {}
    for i in a:
        if i in counts:
            counts[i] += 1
        else:
            counts[i] = 1
    # これだとTLE
    # results = {}
    # for i in a:
    #     if i in results:
    #         print(results[i])
    #         continue
    #     count = 0
    #     for k, v in counts.items():
    #         if k == i:
    #             v -= 1
    #         if v > 1:
    #             count += (v * (v - 1) // 2)
    #     print(count)
    #     results[i] = count
    total = 0
    comb = {}
    for k in counts:
        if counts[k] > 1:
            y = counts[k]
            x = (y * (y - 1)) // 2
            total += x
            comb[k] = x
        else:
            comb[k] = 0
    for i in a:
        print(total - (counts[i] - 1))


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

import math
from functools import reduce
k=int(input())
sum_=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            sum_+=reduce(math.gcd,[i,j,l])
print(sum_)


### FIXED CODE ###

l=[1,9,30,76,141,267,400,624,885,1249,1590,2208,2689,3411,4248,5248,6081,7485,8530,10248,11889,13687,15228,17988,20053,22569,25242,28588,31053,35463,38284,42540,46581,50893,55362,61824,65857,71247,76884,84388,89349,97881,103342,111528,120141,128047,134580,146316,154177,164817,174438,185836,194157,207927,218812,233268,245277,257857,268182,288216,299257,313635,330204,347836,362973,383709,397042,416448,434025,456967,471948,499740,515581,536073,559758,583960,604833,633651,652216,683712,709065,734233,754734,793188,818917,846603,874512,909496,933081,977145,1006126,1041504,1073385,1106467,1138536,1187112,1215145,1255101,1295142,1342852,1373253,1422195,1453816,1502376,1553361,1595437,1629570,1691292,1726717,1782111,1827492,1887772,1925853,1986837,2033674,2089776,2145333,2197483,2246640,2332104,2379085,2434833,2490534,2554600,2609625,2693919,2742052,2813988,2875245,2952085,3003306,3096024,3157249,3224511,3306240,3388576,3444609,3533637,3591322,3693924,3767085,3842623,3912324,4027884,4102093,4181949,4270422,4361548,4427853,4548003,4616104,4718640,4812789,4918561,5003286,5131848,5205481,5299011,5392008,5521384,5610705,5739009,5818390,5930196,6052893,6156139,6239472,6402720,6493681,6623853,6741078,6864016,6953457,7094451,7215016,7359936,7475145,7593865,7689630,7886244,7984165,8130747,8253888,8403448,8523897,8684853,8802826,8949612,9105537,9267595,9376656,9574704,9686065,9827097,9997134,10174780,10290813,10493367,10611772,10813692]
print(l[int(input())-1])
### BUGGY CODE ###

from bisect import bisect_left
a, b, q = map(int, input().split())
INF = 10 ** 11
s = [-INF]
for i in range(a):
    si = int(input())
    s.append(si)
s.append(INF)
t = [-INF]
for i in range(b):
    ti = int(input())
    t.append(ti)
t.append(INF)
x = []
for i in range(q):
    xi = int(input())
    x.append(xi)

for xi in x:
    index_s = bisect_left(s, xi)
    s1 = abs(xi - s[index_s - 1])
    s2 = abs(xi - s[index_s])
    index_t = bisect_left(t, xi)
    t1 = abs(xi - t[index_t - 1])
    t2 = abs(xi - t[index_t])
    print(min(max(s1, t1), max(s2, t2), min(s1, t2) * 2 + max(s1, t2), min(s2, t1) * 2 + max(s2, t1)))


### FIXED CODE ###

import sys
from bisect import bisect_left
inpurt = sys.stdin.readline
a, b, q = map(int, input().split())
INF = 10 ** 11
s = [-INF]
s_append = s.append
for i in range(a):
    si = int(input())
    s_append(si)
s_append(INF)
t = [-INF]
t_append = t.append
for i in range(b):
    ti = int(input())
    t_append(ti)
t_append(INF)
x = []
x_append = x.append
for i in range(q):
    xi = int(input())
    x_append(xi)

for xi in x:
    index_s = bisect_left(s, xi)
    s1 = xi - s[index_s - 1]
    s2 = s[index_s] - xi
    index_t = bisect_left(t, xi)
    t1 = xi - t[index_t - 1]
    t2 = t[index_t] -xi
    print(min(max(s1, t1), max(s2, t2), min(s1, t2) * 2 + max(s1, t2), min(s2, t1) * 2 + max(s2, t1)))
### BUGGY CODE ###

from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for i in range(n):
        for j in reversed(range(item[i][0], min(w+1, x+item[i][0]+1))):
            dp[j] = max(dp[j-item[i][0]]+item[i][1], dp[j])
        x += item[i][0]
    ans = 0
    for i in reversed(range(w+1)):
        if dp[i] > ans:
            ans = dp[i]
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left
def main():
    n, w = map(int, input().split())
    item = [list(map(int, input().split())) for _ in range(n)]
    dp = [0]*(w+1)
    item.sort()
    x = 0
    for p, q in item:
        for j in reversed(range(p, min(w+1, x+p+1))):
            dp[j] = max(dp[j-p]+q, dp[j])
        x += p
    print(max(dp))

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

N = int(input())
A = list(map(int, input().split()))
List = [0] * N

for i in range(N):
  print(str(A.index(i+1)+1), end=" ")






### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
List = [0]*N


for i, a in enumerate(A):
  List[int(a)-1] = str(i+1)

  
print(" ".join(List))
### BUGGY CODE ###

from collections import deque
import sys
import numpy as np

input = sys.stdin.readline
H, W = map(int, input().split())

maze = np.zeros((H, W), dtype='int')


for y in range(H):
    for x, s in enumerate(input()):
        if s=="#":
            maze[y][x] = 1


def bfs(x, y):
    queue = deque([(x, y, 0)])
    visited = np.zeros_like(maze, dtype='int') 

    max_cost = 0
    while queue:
        px, py, cost = queue.popleft()
        max_cost = max(max_cost, cost)

        candidate = ((px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1))
        visited[py][px] = 1
        for cx, cy in candidate:
            if 0 <= cx < W and 0 <= cy < H and visited[cy][cx] == 0 and maze[cy][cx] == 0:
                queue.append((cx, cy, cost + 1))
    
    return max_cost


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == 0:
            ans = max(ans, bfs(x, y))

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

n = int(input())
s = []
for i in range(1,n+1):
  a = i % n
  s.append(a)
ans = sum(s)
print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n+1)//2-n)