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

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = k()
D = l()
M = k()
T = l()

for i in T:
    if i in D:
        D.remove(i)
    else:
        print("NO")
        sys.exit()

print("YES")


### FIXED CODE ###

import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = k()
D = l()
M = k()
T = l()

d = Counter(D)
t = Counter(T)

for i in t:
    if t[i] > d[i]:
        print("NO")
        sys.exit()

print("YES")
### BUGGY CODE ###

import sys
def read():
    return sys.stdin.readline().rstrip()
n, m = map(int, read().split())
A = list(map(int, read().split()))
B = []
for i in range(m):
    b,c = list(map(int, read().split()))
    B.extend([c]*b)
print(sum(sorted(A+B, reverse=True)[:len(A)]))

### FIXED CODE ###

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

B = [[] for _ in range(m)]
for i in range(m):
    B[i] = list(map(int, input().split()))
B.sort(key=lambda x: -x[1])

_A = []
cnt = 0
for i in range(m):
    _A.extend([B[i][1]]*B[i][0])
    cnt += B[i][0]
    if cnt > n:
        break
A += _A
A.sort(reverse=True)
print(sum(A[:n]))
### BUGGY CODE ###

N = int(input())

def f(n):
    if n<6:
        return n
    i,j = 0,0
    a,b = n,n
    while a >= 6:
        i += 1
        a //= 6
    while b >= 9:
        j += 1
        b //= 9
    return min(1+f(n-6**i),1+f(n-9**j))

print(f(N))

### FIXED CODE ###

N = int(input())

memo = {i:i for i in range(6)}
def f(n):
    tmp = memo.get(n,None)
    if tmp != None:
        return tmp
    i,j = 0,0
    a,b = n,n
    while a >= 6:
        i += 1
        a //= 6
    while b >= 9:
        j += 1
        b //= 9
    ret = min(1+f(n-6**i),1+f(n-9**j))
    memo[n] = ret
    return ret

print(f(N))
### BUGGY CODE ###

from collections import deque
from copy import deepcopy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
from copy import copy as dc
import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    g = [[] for i in range(n+1)]
    for i in ab:
        g[i[0]].append(i[1])
        g[i[1]].append(i[0])
    que = deque()
    que.append([1,-1,0,set([1])])
    ans = 0
    while que:
        v, p, cnt, check = que.popleft()
        if cnt >= n - 1:
            if len(check) == n:
                ans += 1
            continue
        for nv in g[v]:
            if nv == p:
                continue
            a = dc(check)
            a.add(nv)
            que.append([nv, v, cnt+1, a])
    print(ans)

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

import sys
 
a = []
for l in sys.stdin:
    if l == '\n':
        break
    else :
        a.append(l)

num = 0
sortedA = []

end = len(a) - 1

for i in range(0, end):
    if i == 0:
        sortedA.append(''.join(sorted(a[1])))
    for j in range(i + 1, end):
        if i == 0:
            sortedA.append(''.join(sorted(a[j + 1])))
        if sortedA[i] == sortedA[j]:
            num = num + 1
print(num)

### FIXED CODE ###

import sys
import collections

n=int(input())
a=[''.join(sorted(input())) for _ in range(n)]

ans = 0
for v in collections.Counter(a).values():
    if v != 1:
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

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

import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K, Q = MAP()
A = np.array([INT() for _ in range(Q)])

point = np.array([K]*N)

for i in range(Q):
	point[A[i] - 1] = point[A[i] - 1] + 1
	point -= 1

a = point >= 1

for i in a:
	if i:
		print("Yes")
	else:
		print("No")

### FIXED CODE ###

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

import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K, Q = MAP()
A = np.array([INT() for _ in range(Q)])

point = [0]*N
for i in range(Q):
	point[A[i] - 1] += 1

for i in range(N):
	if K - Q + point[i] >=1:
		print("Yes")
	else:
		print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(N: int, M: int, A: "List[int]"):
    
    while True:
        A = sorted(A,reverse=True)
        A[0] = A[0] // 2
        M -= 1
        if M == 0:
            break
    print(sum(A))

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
    M = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import heapq

def solve(N: int, M: int, A: "List[int]"):

    while True:
        tmp = heapq.heappop(A) * -1
        heapq.heappush(A,tmp // 2 * -1)
        M -= 1
        if M == 0:
            break
    
    print(sum(A) * -1)

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
    M = int(next(tokens))  # type: int
    A = []
    heapq.heapify(A)
    for i in range(N):
        heapq.heappush(A,int(next(tokens)) * -1)

    solve(N, M, A)

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

from collections import Counter as co
from itertools import combinations as com
n=int(input())
a=0
l=[set(co(input()).items()) for i in range(n)]
for d,s in com(range(n),2):
  if l[d]==l[s]:a+=1
print(a)

### FIXED CODE ###

from collections import Counter as co
from operator import mul
from functools import reduce

def combinations_count(n, r):
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer//denom


n=int(input())
a=0
l=[''.join(list(map(str,sum(sorted(list(map(list,co(input()).items()))),[])))) for i in range(n)]
for d,s in co(l).items():
  if s>=2:a+=combinations_count(s, 2)
print(a)
### BUGGY CODE ###

import sys
H,W,M=map(int, input().split())
h=[]
w=[]
Hcount=[0 for _ in range(H)]
Wcount=[0 for _ in range(W)]
for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    Hcount[hi-1]+=1
    Wcount[wi-1]+=1
h_max=[i for i, v in enumerate(Hcount) if v == max(Hcount)]
w_max=[i for i, v in enumerate(Wcount) if v == max(Wcount)]
#print(h_max,w_max)
for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        h_cand=[k for k, v in enumerate(h) if v == h_max[ii]+1]
        w_cand=[l for l, v in enumerate(w) if v == w_max[jj]+1]
        h_set = set(h_cand)
        w_set = set(w_cand)
        matched_list = list(h_set & w_set)
        #print(h_cand,w_cand)
        #print(matched_list)
        if len(matched_list)==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)


### FIXED CODE ###

import sys
 
input = sys.stdin.readline
 
 
def main():
    H, W, M = map(int, input().split())
    row = [0] * (H)
    col = [0] * (W)
    bomb = set()
    for _ in range(M):
        h, w = map(int, input().split())
        bomb.add((h, w))
        row[h-1] += 1
        col[w-1] += 1
    row_max = max(row)
    row_index_list = [i for i, v in enumerate(row) if v == row_max]
    col_max = max(col)
    col_index_list = [i for i, v in enumerate(col) if v == col_max]
    ans = row_max + col_max - 1
    c = False
    for x in row_index_list:
        for y in col_index_list:
            if not (x + 1, y + 1) in bomb:
                c = True
                break
        if c:
            break
    if c:
        ans += 1
    print(ans)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
d = deque()

for _ in range(int(input())):
    s = input().split()
    
    if s[0] == 'insert':
        d.appendleft(int(s[1]))
    elif s[0] == 'delete':
        try:
            d.remove(int(s[1]))
        except:
            pass
    elif s[0] == 'deleteFirst':
        d.popleft()
    elif s[0] == 'deleteLast':
        d.pop()

print(*d)



### FIXED CODE ###

import collections
a=collections.deque()
for _ in range(int(input())):
    b=input()
    if b[0]=='i':a.appendleft(b[7:])
    elif b[6]==' ':
        try:a.remove(b[7:])
        except:pass
    elif len(b)>10:a.popleft()
    elif len(b)>6:a.pop()
print(*a)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
e = 0
max_e = 0

for i in range(0, N-K+1):
    e = 0
    for j in range(i, i+K):
        e += (P[j] + 1) / 2
    max_e = max(e, max_e)

print(max_e)


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
S = []

for num in P:
    S.append((num + 1) / 2)

ans = sum(S[0:K])
max_ans = ans

for i in range(N-K):
    ans = ans - S[i] + S[i+K]
    max_ans = max(ans, max_ans)

print(max_ans)
### BUGGY CODE ###

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


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    lcm = a[0]
    ans = 0

    for ai in a[1:]:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai

    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    lcm = 1
    ans = 0

    for ai in a:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai

    print(ans % mod)


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

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

def simulate():
    global A
    B = [0]*N
    for i in range(N):
        l = max(0, i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    if sum(B) == N*K:
        print(*[N]*N)
        exit()
    A = B

for k in range(K):
    simulate()
print(*A)

### FIXED CODE ###

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

def simulate():
    global A
    B = [0]*N
    for i in range(N):
        l = max(0, i-A[i])
        r = min(N-1, i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    for i in range(1,N):
        B[i] += B[i-1]
    # if sum(B) == N*K:
    #     print(*[N]*N)
    #     print('aaaa')
    #     exit()
    A = B

for k in range(min(K,43)):
    simulate()
print(*A)
### BUGGY CODE ###


a = int(input())
b = input()

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        if c[i] == "1":
            nsum += n
            if n > x:
                n = n % x
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum))

for i in range(a):
    s = list(b)
    s[i] = "0" if s[i] == "1" else "1"
    c = "".join(s)
    print(str(func(c)))

### FIXED CODE ###

from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))
### BUGGY CODE ###

N= int(input())
Ai=list(map(int,input().split()))
for i in range(N):
    print(Ai.count(i+1))

### FIXED CODE ###

import collections
N= int(input())
Ai=list(map(int,input().split()))
c=collections.Counter(Ai)

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

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

import numpy
import scipy
#import sys


N, Y = map(int, input().split())

find = False
for x in range(N+1):
    for y in range(N+1-x):
        for z in range(N+1-x-y):
            sum = x*10000 + y*5000 + z*1000
            if sum == Y and not find:
                find = True
                print("{} {} {}".format(x, y, z))
                #sys.exit()

if not find:
    print("-1 -1 -1")


### FIXED CODE ###

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

import numpy
import scipy
#import sys


N, Y = map(int, input().split())

find = False
for x in range(N+1):
    for y in range(N+1-x):
        z = N - x - y
        if find:
            break
        sum = x*10000 + y*5000 + z*1000
        if sum == Y:
            find = True
            print("{} {} {}".format(x, y, z))
            #sys.exit()

if not find:
    print("-1 -1 -1")
### BUGGY CODE ###

N = int(input())
ans = 0

for i in range(1, N):
    ans += i

print(ans)


### FIXED CODE ###

N = int(input())
print((N - 1) * N // 2)
### BUGGY CODE ###

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

n = int(input())

a = list()
for i in range(n):
    a.append(int(input()))

a_sorted = sorted(a, reverse=True)

for i in range(n):
    index = a_sorted.index(a[i])
    if index == 0:
        print(a_sorted[index + 1])
        continue

    print(a_sorted[0])


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
    n = int(input())

    a = [None] * n
    for i in range(n):
        a[i] = int(input())

    a_sorted = sorted(a, reverse=True)
    a_max = max(a)

    for i in a:
        if i != a_max:
            print(a_max)
            continue

        index = a_sorted.index(i)
        if index == 0:
            print(a_sorted[index + 1])


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

# 1. 入出力 (二次元配列)

N, C = map(int, input().split())

D = [ list(map(int, input().split())) for _ in range(C) ]
col = [ list(map(int, input().split())) for _ in range(N) ]

ans = 1 << 60
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or k == i:
                continue

            temp = 0
            lst = [i, j, k]

            for x in range(N):
                for y in range(N):
                    mod = (x + y) % 3
                    temp += D[ col[x][y] - 1 ][ lst[mod] ]

            ans = min(ans, temp)
            # print(lst, temp)

print(ans)

### FIXED CODE ###

# 1. 入出力 (二次元配列)

N, C = map(int, input().split())

D = [ list(map(int, input().split())) for _ in range(C) ]
col = [ list(map(int, input().split())) for _ in range(N) ]

ans = 1 << 60
info = [ [0 for j in range(C)] for i in range(3) ]

for i in range(N):
    for j in range(N):
        mod = (i + j) % 3
        info[mod][ col[i][j] - 1 ] += 1

for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or j == k or k == i:
                continue

            temp = 0
            lst = [i, j, k]

            for x in range(3):
                for y in range(C):
                    temp += D[y][ lst[x] ] * info[x][y]

            ans = min(ans, temp)
            # print(lst, temp)

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

n=int(input())
a=list(map(int,input().split()))
m=int(input())
b=list(map(int,input().split()))
c=0
for i in range(m):
    if b[i] in a:
        a[a.index(b[i])]=0
    else:
        c=1
print("YES"if c!=1else"NO")

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a=Counter(a)
m=int(input())
b=list(map(int,input().split()))
b=Counter(b)
for d,e in b.items():
    if a[d]<e:
        print("NO")
        exit()
print("YES")
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
res = 0
ans = 0
for i in range(1,N+1):
    res_bar = math.floor((A*i)/B)-A*math.floor(i/B)
    if res_bar >= res:
        res = res_bar
        ans = i
    else:
        break
        
        
print(res)
    

      

### FIXED CODE ###

import math
 
a, b, n = map(int, input().split())
ans = 0
tmp = 0
 
if n > b - 1:
    n = b-1
 
ans = math.floor(a*n/b) - a*math.floor(n/b)
 
print(ans)
### BUGGY CODE ###

s = input()
count = 0

while ("01" in s) | ("10" in s):
    if "01" in s:
        s = s.replace("01","", 1)
    else:
        s = s.replace("10","", 1)
    count += 2
print(count)

### FIXED CODE ###

s = input()
print(2 * min(s.count("0"), s.count("1")))
### BUGGY CODE ###

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

mod = 10**9 + 7

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
def modinv(x):
    return pow(x, mod-2)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = 2 * n - 1 #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod
    factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
    # n! / (k! * (n-k)! )
    if k <= 0 or k >= n:
        return 1
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)


### FIXED CODE ###

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

mod = 10**9 + 7

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
def modinv(x):
    return pow(x, mod-2, mod)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = 2 * n - 1 #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod
    factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
    # n! / (k! * (n-k)! )
    if k <= 0 or k >= n:
        return 1
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod

if k >= n-1:
    # nHn = 2n-1 C n
    print(binomial_coefficients(2 * n - 1, n))
else:
    # 移動がk回←→ 人数0の部屋がk個以下
    # 人数0の部屋がちょうどj個のものは
    # nCj(人数0の部屋の選び方) * jH(n-j) (余剰のj人を残りの部屋に入れる)
    ans = 0
    for j in range(k+1):
        if j == 0:
            ans += 1
        else:
            ans += binomial_coefficients(n, j) * binomial_coefficients(n-1, j) 
            ans %= mod
    print(ans)
### BUGGY CODE ###

N = int(input())
t = N
ans = 0
while t > 0:
  tt = t
  while tt > 0:
    if tt % 2019 == 0:
      ans += 1
    tt //= 10
  t = t % pow(10, len(str(t))-1)
print(ans)

### FIXED CODE ###

S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10
  digits %= 2019

for i in range(2019):
  ans += mod_list[i] * (mod_list[i] - 1) // 2
  
print(ans)
### BUGGY CODE ###

N=int(input())
A=sorted(list(map(int,input().split())))
l=len(A)
ans=0
for i in range(l):
  if i>0 and A[i-1]==A[i]:
    continue
  flag=0
  for j in range(l):
    if i==j:
      continue
    if A[j] > A[i]:
      break
    if A[i]%A[j]==0:
      flag=1
      break
  if flag==0:
    ans+=1
print(ans)


### FIXED CODE ###

#https://at274.hatenablog.com/entry/2020/06/29/181102
import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
A=set(A)
MAX_A=10**6
X=[0]*(MAX_A + 1)#0-MAX_Aまでの整数がAの倍数で何回割られるか
for i in A:
  for j in range(i,MAX_A + 1,i):
    X[j]+=1

#割られた回数が1つしかないものはその数自身で割ったのでカウント
#ただし複数ある場合は除外
ans = len([a for a in A if (X[a] == 1) and (c[a] == 1)])
print(ans)
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[0]*(W+1)
for _ in range(N):
    w,v=map(int,input().split())
    for i in range(W,w-1,-1):
        tmp=dp[i-w]+v
        if tmp>dp[i]:
            dp[i]=tmp
print(dp[W])


### FIXED CODE ###

def opt(N,W):
    dp=[0]*(W+1)
    for _ in range(N):
        w,v=map(int,input().split())
        for i in range(W,w-1,-1):
            tmp=dp[i-w]+v
            if tmp>dp[i]:
                dp[i]=tmp
    print(dp[W])

N,W=map(int,input().split())
opt(N,W)