Harryxun/stf_run huggingface dataset:
def solve():
  import sys

  sys.setrecursionlimit(10**7)
  readline = sys.stdin.readline

  
  n = int(readline())
  a = [list(map(int,readline().split())) for _ in range(n)]
  c = [0]*n
  d = 0
  m = list(range(n))
  
  while m:
    candidate = set()
    for i in m:
      if i in candidate:
        continue
      j = a[i][c[i]]-1
      if a[j][c[j]]-1 == i:
        candidate.add(i)
        candidate.add(j)

    if candidate:
      for i in candidate:
        c[i]+=1
        if c[i] == n-1:
          m.remove(i)
      d+=1
    else:
      d=-1
      break
      
  print(d)


if __name__ == '__main__':
  solve()

### FIXED CODE ###

def solve():
  import sys
  import math

  sys.setrecursionlimit(10**7)

  a = input()
  b = input()
  
  print(sum(a[i]==b[i] for i in range(3)))


if __name__ == '__main__':
  solve()
nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]
slist = []
clist = []
for i in range(m):
  sc = [int(i) for i in input().split()]
  slist.append(sc[0])
  clist.append(sc[1])

fl = 0
if (n == 1):
  if (slist[0] == 1 and clist[0] == 0):
    print('0')
    fl = 1

answerlist = ['-1' for i in range(n)]
for (i,s), c in zip(enumerate(slist),clist):
  if (c == 0 and s == 1):
    print('-1')
    break
    fl = 1
  if (answerlist[s-1] != '-1' and answerlist[s-1] != str(c)):
    print('-1')
    break
    fl = 1
  answerlist[s-1] = str(c)
for i in range(n):
  if (answerlist[i]) == '-1':
    if (i == 0):
      answerlist[i] = '1'
    else:
      answerlist[i] = '0'
if fl == 0:
	print("".join(answerlist))

### FIXED CODE ###

nm = [int(i) for i in input().split()]
n = nm[0]
m = nm[1]
slist = []
clist = []

for i in range(m):
  sc = [int(i) for i in input().split()]
  slist.append(sc[0])
  clist.append(sc[1])

fl = 0
if (n == 1):
  if m != 0:
    if (slist[0] == 1 and clist[0] == 0):
      print('0')
      fl = 1
      exit()

answerlist = ['-1' for i in range(n)]
for (i,s), c in zip(enumerate(slist),clist):
  if (c == 0 and s == 1):
    print('-1')
    fl = 1
    exit()
  if (answerlist[s-1] != '-1' and answerlist[s-1] != str(c)):
    print('-1')
    fl = 1
    exit()
  answerlist[s-1] = str(c)
for i in range(n):
  if (answerlist[i]) == '-1':
    if (i == 0):
      if (n == 1):
        answerlist[i] = '0'
      else:
        answerlist[i] = '1'
    else:
      answerlist[i] = '0'
if fl == 0:
	print("".join(answerlist))
import string

S = input()
alphabets = list(string.ascii_lowercase)
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        for i in S:
            if alphabets[i] != S[i]:
                print(S[:i] + alphabets[i])
                break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break

### FIXED CODE ###

import string

S = input()
reversedS = ''.join(list(S)[::-1])
alphabets = list(string.ascii_lowercase)
lastWord = ''.join(alphabets[::-1])
cnt = [S.count(chr(ord('a')+i)) for i in range(26)]
if len(S) == 26:
    if S == lastWord: print(-1)
    else:
        found = False
        for i in range(len(reversedS)):
            s = reversedS[i]
            largeS = alphabets[ord(s)-ord('a')+1:]
            tailS = list(S)[26-i-1:]
            for lS in largeS:
                if lS in tailS:
                    print(S[:26-i-1]+lS)
                    found = True
                    break
            if found: break
else:
    for j in range(26):
        if cnt[j] == 0:
            S += chr(ord('a')+j)
            print(S)
            break
S = input()

from collections import defaultdict

dic = defaultdict(int)

for s in S:
    dic[s] += 1
    
if len(dic) == 2:
    for k, v in dic:
        if v == 2:
            continue
        else:
            print("No")
            exit()
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
if len(set(list(S))) == 2:
    tmp = list(set(list(S)))
    if S.count(tmp[0]) == 2 and  S.count(tmp[1]) == 2:
        print("Yes")
    else:
        print("No")

else:
    print("No")
#!/usr/bin/env python3

def main():
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            if c in color_used[j]:
                continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

if __name__ == "__main__":
    main()
n = int(input())
a = map(int,input().split())
b = map(int,input().split())



c = [0]*(n)
for i in range(n):
    if i > 1 and a[i] < b[i]:
        c[i] = min(a[i] + a[i + 1], b[i])
    else:
        c[i] = min(a[i] + a[i + 1] - c[i - 1], b[i])
print(sum(c))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = 0
cnt = 0
for i in range(n):
  c = min(a[i] + a[i+1],b[i])
  if b[i] > a[i]:
    a[i+1] = a[i] + a[i+1] - c
  cnt += c
print(cnt)
n,k=map(int,input().split())
while n>=0:
  if n-k<=0:
    print(max(abs(n-k),n)
    break
  n=n-k

### FIXED CODE ###

n,k=map(int,input().split())
print(min(n%k,abs(n%k-k)))
def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            while (DP2[i][j] > mod):
                DP2[i][j] -= mod
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()
A = [int(input()) for i in range(5)]
#１の位が１～９のうちで1に近いほど、最後に調理される
B = [a-a%10+10 if a % 10 != 0 else a for a in A]
diff = [(b-a) for a,b in zip(a,b)]
print(sum(B) - max(diff))

### FIXED CODE ###

A = [int(input()) for i in range(5)]
#１の位が１～９のうちで1に近いほど、最後に調理される
B = [a-a%10+10 if a % 10 != 0 else a for a in A]
diff = [(b-a) for a,b in zip(A,B)]
print(sum(B) - max(diff))
n = int(input())
s = list(map(int,input().split()))
for i in range(len(s)-1,0,-1):
    if(s[i]>s[i-1]):
        continue
    else:
        s[i-1] = s[i]
print(sum(s)+s[0])
        

### FIXED CODE ###

n = int(input())
print(n**3)
n = input()
if(n == 1):
  print("Hello World")
else:
  print(input() + input())


### FIXED CODE ###

if(input() == "1"):
  print("Hello World")
else:
  print(int(input()) + int(input()))
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1) :
    w, v = wv[i-1]
    for j in range(W+1) :
        if j < w :
            dp[i][j] = dp[i-1][j]
        else :
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - w] + v)
            
print(dp[N][W])

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

s = [[] for _ in range(4)]
w0 = wv[0][0]
for w, v in wv :
    s[w-w0].append(v)
for i in range(4) :
    s[i].sort(reverse=True)
    s[i] = [0] + s[i]
    for j in range(1, len(s[i])) :
        s[i][j] += s[i][j-1]

M = 0
for i0 in range(len(s[0])) :
    for i1 in range(len(s[1])) :
        for i2 in range(len(s[2])) :
            for i3 in range(len(s[3])) :
                if i0*w0+i1*(w0+1)+i2*(w0+2)+i3*(w0+3) <= W :
                    M = max(M, s[0][i0]+s[1][i1]+s[2][i2]+s[3][i3])
                    
print(M)
import math
import collections
import fractions
import itertools

def solve():
    n=int(input())
    ans=''
    check='abcdefghijklmnopqrstuvwxyz'
    while n!=0:
        n-=1
        ans+=check[n%26]
        print(ans[::-1])
    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

def solve():
    n=int(input())
    ans=''
    check='abcdefghijklmnopqrstuvwxyz'
    while n!=0:
        n-=1
        ans+=check[n%26]
        n //= 26
    print(ans[::-1])
    return 0

if __name__ == "__main__":
    solve()
import sys
a = map(int, input().split())

print(3*a**2)

### FIXED CODE ###

import sys
a = int(input())
print(3*a**2)
print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())-1]

### FIXED CODE ###

print([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51][int(input())-1])
S=input()
T=input()

print(T+S)

### FIXED CODE ###

S,T=map(str,input().split())


print(T+S)
def main(str):
  print("{}{}{}".format(str[0],str(len(str)-2),str[len(str)-1])

### FIXED CODE ###

s = input()
print("{}{}{}".format(s[0],len(s)-2,s[-1]))
N = int(input())
tmp = [0,0,0]
data=list(map(int,(input()).split()))
flag = True
for i in range(N):
  tmp = list(map(int,(input()).split()))
  if (tmp[0] - data[0])%2 == (tmp[1] + tmp[2] - data[1] - data[2]) % 2 + 1:
    flag = False
    break
  else:
    data = tmp

if flag:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
tmp = [0,0,0]
data = [0,0,0]
flag = True
for i in range(N):
  tmp = list(map(int,(input()).split()))
  if (tmp[0] - data[0])%2 == (tmp[1] + tmp[2] - data[1] - data[2]) % 2 + 1 or (tmp[1] - data[1] + tmp[2] - data[2] > tmp[0] - data[0]):
    flag = False
    break
  else:
    data = tmp

if flag:
  print("Yes")
else:
  print("No")
def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(x))
  cxmod=dict(Counter(xmod))
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in cxmod.keys():
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()



### FIXED CODE ###

def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  #xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod={}
  for k in cx:
    if k%m in cxmod:
      cxmod[k%m]+=cx[k]
    else:
      cxmod[k%m]=cx[k]
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()
# -*- coding: utf-8 -*-

n, x, m = map(int, input().split())

a_list = [x]
a = x
i = 1
while (i<n and i < m):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    
#print(i)
#print(a_list)
    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    #print(blen)
    #print(amari)
    #print(sum1, sum2, repeat, sum3)

print(ans)

### FIXED CODE ###

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

n, x, m = map(int, input().split())

a_list = [x]
a = x
i = 1
while (i<n and i < m+1):
    a = (a*a) % m
    a_list.append(a)
    i += 1
    
#print(i)
#print(a_list)
    
if i == n:
  ans = sum(a_list)
else:
    b = a_list.index(a)
    sum1 = sum(a_list[:b+1])
    sum2 = sum(a_list[b+1:i])
    blen = i-b-1
    repeat = (n-b-1) // blen
    amari = (n-b-1) % blen
    sum3 = 0
    if amari != 0:
    	sum3 = sum(a_list[b+1:b+amari+1])
    ans = sum1 + sum2*repeat + sum3
    #print(blen)
    #print(amari)
    #print(sum1, sum2, repeat, sum3)

print(ans)
s=input()
r=set()
last=0
power=1
d={0:0}
total=0
for i in range(len(s)-1,-1,-1):
    n=int(s[i])*power+rem
    power*=10
    power=power%2019
    rem=n%2019
    if rem in r:
        d[rem]+=1
        total+=d[rem]-1
    else:
        r.add(rem)
        d[rem]=1
if d[0]==1:
    print(total+1)
else:
    print(total)







### FIXED CODE ###

s=input()
r=set()
last=0
power=1
d={0:0}
total=0
rem=0
for i in range(len(s)-1,-1,-1):#handling of 0's as n and rem
    n=int(s[i])*power+rem
    power*=10
    power=power%2019
    rem=n%2019
    if rem in d.keys():
        d[rem]+=1
    else:
        d[rem]=1
    total+=d[rem]-1
print(total+d[0])
import math
import numpy as np
H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
  n,a=input().split()
  A.append(int(n))
  B.append(int(a))
C=[]
for i in range(N):
  C.append(A[i]/B[i])
sub=0
for i in range(N):
  if C[i]>=C[sub]:
    sub=i
sub2=math.ceil(H/A[sub])
sub3=sub2*B[sub]
for ia in range(H,sub2*A[sub]):
  t = ia
  M = len(A) - 1
  elm = []
  for i, step in enumerate(A):
    temp = [1] * (M - i)
    elm.append(np.arange(0, t+1, step).reshape(-1, *temp))
  res = 0
  for x in elm:
    res = res + x
  for x in np.argwhere(res == t):
    sub4=0
    for ib in range(N):
      sub4+=B[ib]*x[ib]
    if sub4<=sub3:
      sub3=sub4
print(sub3)

### FIXED CODE ###

H,N=map(int,input().split())
A=[]
B=[]
for i in range(N):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
def f(x):
    if x<=0:
        return 0
    else:
        mini=g(x-A[0])+B[0]
        for i in range (1,N):
            sub=g(x-A[i])+B[i]
            if sub<mini:
                mini=sub
        return mini
def g(x):
    if x<0:
        return 0
    else:
        return g_list[x]
g_list=[]
g_list.append(0)
for i in range(1,H+1):
    g_list.append(f(i))
print(g_list[-1])
# -*- coding: utf-8 -*-

a, b, k = map(int, input().split())

aa = ''.join(map(str, (list(range(a, b+1)))))

cc = aa[0:k]
dd = aa[len(aa)-k:]

cc = [int(i) for i in cc]
dd = [int(i) for i in dd]

ee = set()

for i in cc+dd:
    ee.add(i)

ee = sorted(list(ee))

for i in ee:
    print(i)


### FIXED CODE ###

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

a, b, k = map(int, input().split())

if b-a < 2*k:
    for i in range(a, b+1):
        print(i)
else:
    for i in range(a, a+k):
        print(i)
    for i in range(b-k+1, b+1):
        print(i)
import numpy as np
import collections

def main():
    n = int(input())
    ball = [list(map(int, input().split(' '))) for i in range(n)]
    ball = np.array(ball, dtype=int)
    # print(ball)

    l1 = []
    l2 = []
    for i in range(n):
        for j in range(i, n):
            if i == j: continue
            dis1 = ball[i] - ball[j]
            dis2 = ball[j] - ball[i]
            l1.append(list(dis1))
            l2.append(list(dis2))
    # print(l1, l2)
    # c1 = collections.Counter(l1)
    # c2 = collections.Counter(l2)

    c1 = []
    c2 = []
    for i in range(len(l1)):
        c1.append(l1.count(l1[i]))
        c2.append(l2.count(l2[i]))
    m1 = np.max(np.array(c1, dtype=int))
    m2 = np.max(np.array(c2, dtype=int))

    print(max(1,n-max(m1,m2)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
from sys import stdin

def main():
    n, k = [int(x) for x in stdin.readline().rstrip().split()]
    if k == 1: print(0)
    else: print(n-k)

if __name__ == "__main__":
    main()
import numpy as np
import sys
input = sys.stdin.readline

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

dp = np.zeros((N, W+1), dtype='int64')

for i in range(N):
    wi, vi = map(int, input().split())

    dp[i][:wi] = dp[i-1][:wi]
    dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)

print(dp[N-1][W])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
vmax = 1000*100+1
wmax = 100*10**9
dp = [wmax] * vmax
dp[0] = 0
 
for i in range(N):
    wi, vi = map(int, input().split())
    ndp = dp[:]
    for j in range(vi, vmax):
        ndp[j] = min(dp[j], dp[j-vi] + wi)
    dp = ndp

v = 0
for i, w in enumerate(dp):    
    if w == wmax:
        continue
    if w <= W:
        v = i
print(v)
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common = 1
for i in range(len(A)):
    common = common * a // math.gcd(common, A[i])

ans = 0
for i in range(len(A)):
    ans += common // A[i]
    ans %= MOD

print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

print(ans)
a = int(raw_input())
print(48 - a)

### FIXED CODE ###

import fileinput
for line in fileinput.input():
    print(48 - int(line))
n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
INF = 1000000007

dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0

for i in range(2,n+1):
    if i not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
      dp[i] += dp[i-2] #n-2 段目が安全なら
dp[i] %= INF

print(dp[n])

### FIXED CODE ###

n,m = map(int,input().split())
a = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
INF = 1000000007

dp[0] = 1
if 1 not in a:
  dp[1] = 1

for i in range(2,n+1):
    if i-1 not in a :
      dp[i] += dp[i-1] #n-1 段目が安全なら
    if i-2 not in a :
      dp[i] += dp[i-2] #n-2 段目が安全なら
    dp[i] %= INF

print(dp[n])
N,M,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
 
a, b =[0],[0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
 
ans, j =0,M
for i in range(N+1):
  while b[j] > K-a[i]:
        j -= 1
  ans = max(ans, i+j)
print(ans)

### FIXED CODE ###

N,M,K = map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
 
a, b =[0],[0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
 
ans, j =0,M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K-a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)