Harryxun/stf_run huggingface dataset:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from math import gcd

    n0, m0 = list(map(int, readline().split()))
    a0 = list(map(int, readline().split()))
    ahalf = [x // 2 for x in a0]
    ans = 0

    if all([x % 2 == 0 for x in ahalf]):
        if all([(x - ahalf[0]) % 4 == 0 for x in ahalf]):
            lcm = a0[0]
            for elem in a0[1:]:
                lcm = (lcm * elem) // gcd(lcm, elem)
            ans = (m0 + (lcm // 2)) // lcm
    elif all([x % 2 == 1 for x in ahalf]):
        lcm = a0[0]
        for elem in a0[1:]:
            lcm = (lcm * elem) // gcd(lcm, elem)
        ans = (m0 + (lcm // 2)) // lcm

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from fractions import gcd

    n, m = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    cnt = [0] * n

    for i, elem in enumerate(a):
        x = elem
        c = 0
        while x % 2 == 0:
            x //= 2
            c += 1
        cnt[i] = c

    ans = 0

    if len(set(cnt)) == 1:
        lcm = a[0]
        for elem in a[1:]:
            lcm = (lcm * elem) // gcd(lcm, elem)
        ans = (m + (lcm // 2)) // lcm

    print(ans)


if __name__ == '__main__':
    main()
mnum, gnum = map(int, input().split())
array = list(map(int, input().split()))

for i in range(gnum):
	array.sort()
	array[len(array)-1] = array[len(array)-1]/2

print(sum(array))

### FIXED CODE ###

text = input()

result = ''
if text == 'Sunny':
	result = 'Cloudy'
elif text == 'Cloudy':
	result = 'Rainy'
else:
	result = 'Sunny'
    
print(result)
n=input()
t,a=map(int,input().split())
h=list(map(int,input()))
h2=[t-x*0.006 for x in h]
print(h2.index(min(h2))+1)
    
    

### FIXED CODE ###

n=int(input())
t,a=map(int,input().split())
h=list(map(int,input().split()))
h2=[abs(t-x*0.006-a) for x in h]
print(h2.index(min(h2))+1)
def mizuyari2(l):
    count = 0
    stopper = 0

    for i in l:
        stopper+=i 
    if(stopper == 0):
        return 0        

    if(l[0]!=0):
        count+=1
    for i in range(len(l)-1):
        if(l[i]==0 and l[i+1]!=0):
            count+=1

    for index,i in enumerate(l):           
        l[index]-=1
        if(l[index]<0):
            l[index]=0

    return count+mizuyari2(l)

N = int(input())
h = []

for i in range(N):
    h.append(int(input()))

print(mizuyari2(h))

### FIXED CODE ###

import array
def count_mizuyari(l):
    count = 0
    arr = array.array('i',[0])
    arr.extend(l)
    for i in range(len(arr)-1):
        if(arr[i]==0 and arr[i+1]!=0):
            count += 1
    return count
    

def mizuyari2(l):
    count = 0
    stopper = 0

    #要素が全部0かどうかの判定
    for i in l:
        stopper+=i 
    if(stopper == 0):
        return 0 
    else:     
        count=count_mizuyari(l)
    for index,i in enumerate(l):           
        l[index]-=1
        if(l[index]<0):
            l[index]=0

    return count+mizuyari2(l)

N = int(input())
h = array.array('i')

li = input().rstrip().split()
for i in li:
    h.append(int(i))


print(mizuyari2(h))
H, W = map(int, input().split())
l = []
for h in range(H):
    l.append(input())

for h in range(H):
    for w in range(W):
        if l[h][w] == "#":
            j = False
            if h != 0:
                if l[h - 1][w] == "#":
                    j = True
            if h != H - 1:
                if l[h + 1][w] == "#":
                    j = True
            if w != 0:
                if l[h][w - 1] == "#":
                    j = True
            if w != W - 1:
                if l[h][w + 1] == "#":
                    j = True
            if not j:
                break
if j:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

H, W = map(int, input().split())
l = []
for h in range(H):
    l.append(input())

j = True
for h in range(H):
    if not j:
        break
    for w in range(W):
        if l[h][w] == "#":
            j = False
            if h != 0:
                if l[h - 1][w] == "#":
                    j = True
            if h != H - 1:
                if l[h + 1][w] == "#":
                    j = True
            if w != 0:
                if l[h][w - 1] == "#":
                    j = True
            if w != W - 1:
                if l[h][w + 1] == "#":
                    j = True
            if not j:
                break
if j:
    print("Yes")
else:
    print("No")
_ = input()
num_list = list(map(int, input().split()))

res = 0

for num in range(num_list):
  count = 0
  
  while(num % 2  == 0):
    num /= 2
    count += 1
  
  if count > res:
    res = count
    
print(res)

### FIXED CODE ###

_ = input()
num_list = list(map(int, input().split()))

res = 1000000

for num in num_list:
  count = 0
  
  while(num % 2  == 0):
    num /= 2
    count += 1
  
  if count < res:
    res = count
    
print(res)
s=str(input())
y=700
x=0
while x!=2
if s[x]=o：
　　　y+100
x+=1

print(y)

### FIXED CODE ###

S = input()
s = S.count('o')*100
 
print(700+s)
A,B,C=map(int,input().split())
#print(sorted(B)[0])
if b-a==c-b:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

a,b,c=map(int,input().split())
#print(sorted(B)[0])
if b-a==c-b:
    print('YES')
else:
    print('NO')
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import statistics
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

def main():
  S = input()
  Q = int(input())
  TFC = list(list(input().split()) for _ in range(Q))
  rev = 0
  q = deque(S)
  for i in range(Q):
    if TFC[i][0] == '1':
      rev ^= 1
    else:
      if TFC[i][1] == '1':
        if rev == 0:
          q.appendleft(TFC[i][2])
        else:
          q.append(FC[i][2])
      else:
        if rev == 0:
          q.append(TFC[i][2])
        else:
          q.appendleft(TFC[i][2])
  ans = ''.join(q)
  print(ans if rev==0 else ans[::-1])
  
if __name__ == '__main__':
  main()

### FIXED CODE ###


from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import statistics
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm(a, b):
  return a*b//gcd(a, b)

def main():
  S = input()
  Q = int(input())
  TFC = list(list(input().split()) for _ in range(Q))
  rev = 0
  q = deque(S)
  for i in range(Q):
    if TFC[i][0] == '1':
      rev ^= 1
    else:
      if TFC[i][1] == '1':
        if rev == 0:
          q.appendleft(TFC[i][2])
        else:
          q.append(TFC[i][2])
      else:
        if rev == 0:
          q.append(TFC[i][2])
        else:
          q.appendleft(TFC[i][2])
  ans = ''.join(q)
  print(ans if rev==0 else ans[::-1])
  
if __name__ == '__main__':
  main()
N,P=map(int,input().split())
for x in range(int(pow(P,1/N))+1,0,-1):
  if P%(x**N)==0:
    print(x)
    exit()


### FIXED CODE ###

def primes(n):
  ps = {}
  while n%2==0:
    n//=2
    if 2 not in ps:
      ps[2] = 1
    else:
      ps[2] += 1
  
  for i in range(3,int(n**.5)+1,2):
    while n%i==0:
      n//=i
      if i not in ps:
        ps[i] = 1
      else:
        ps[i] += 1
  
  if n!=1:
    ps[n] = 1
  
  return ps
  
N,P = map(int,input().split())
if N==1:
  print(P)
  exit()
ps = primes(P)
ans = 1
for p, num in ps.items():
  if num>=N:
    ans *= p**(num//N)
print(ans)
H,W = list(map(int,input().split()))
data = [list(input()) for l in range(H)]
visit = [[0 for i in range(W)] for j in range(H)]
sum = 0
def search(i,j,col):
    global H,W,data,visit,sum
    if (i < 0)or(i >= H)or(j < 0)or(j >= W):
        return
    if (i >= 0)and(i <= H-1)and(j >= 0)and(j <= W-1):
        if (visit[i][j]):return
        if (col == '#') and (data[i][j] == '.'):
            sum += 1
            visit[i][j] = 1
        elif (col == '.') and (data[i][j] == '#'):
            visit[i][j] = 1
        elif (col == ''):
            visit[i][j] = 1
        else:return
    
            
    if data[i][j] == '#':
        search(i-1,j,'#')
        search(i,j-1,'#')
        search(i,j+1,'#')
        search(i+1,j,'#')
    if data[i][j] == '.':
        search(i-1,j,'.')
        search(i,j-1,'.')
        search(i,j+1,'.')
        search(i+1,j,'.')
    

for i in range(H):
    for j in range(W):
        if data[i][j] == '#':
            visit = [[0 for i in range(W)] for j in range(H)]
            search(i,j,'')

print(sum)

### FIXED CODE ###

import math
H,W = list(map(int,input().split()))
data = [list(input()) for l in range(H)]
check = [[0 for s in range(W)] for k in range(H)]
sum = 0

def search(i,j,H,W,data,check):
    stack = [[i,j]]
    check[i][j] = 1 
    tempSum = 0
    numW = 0
    numB = 0
    while True:
        if len(stack) != 0:
            s = stack[-1]
            hNow,wNow = s[0],s[1]
            WB = data[hNow][wNow]
            if WB == '.':
                numW += 1
            else:
                numB += 1
        else:
            return (numW*numB),check


        stack.pop()

        if hNow < H-1:
            if (data[hNow+1][wNow] != WB) and (check[hNow+1][wNow] == 0):
                stack.append([hNow+1,wNow])
                check[hNow+1][wNow] = 1
        if wNow < W-1:
            if (data[hNow][wNow+1] != WB) and (check[hNow][wNow+1] == 0):
                stack.append([hNow,wNow+1])
                check[hNow][wNow+1] = 1

        if hNow > 0:
            if (data[hNow-1][wNow] != WB) and (check[hNow-1][wNow] == 0):
                stack.append([hNow-1,wNow])
                check[hNow-1][wNow] = 1

        if wNow > 0:
            if (data[hNow][wNow-1] != WB) and (check[hNow][wNow-1] == 0):
                stack.append([hNow,wNow-1])
                check[hNow][wNow-1] = 1
        
for i in range(H):
    for j in range(W):
        if (check[i][j] == 0):
            temp,check = search(i,j,H,W,data,check)
            sum += temp

print(sum)
W, H, N = map(int, input().split())

xy = [0, W, 0, H]
judge = True
for n in range(N):
    x, y, a = map(int, input().split())
    a -= 1
    if a<=1 and judge:
        xy[a] = x
        if xy[0] >= xy[1]:
            judge = False
    else:
        xy[a] = y
        if xy[2] >= xy[3]:
            judge = False
    print(xy)
area = (xy[1] - xy[0]) * (xy[3] - xy[2])
if not judge:
    area = 0
    print(area)

### FIXED CODE ###

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

li = sorted([a, b, c])
ans = 'No'
if sum(li[:2])==li[2]:
    ans ='Yes'
print(ans)
s = str(input())
 
if s[0] != 'A':
    print('WA')
    break
else:
    for i in range(len(s)-1):
        if s[i] == 'C':
            s = s[1:i-1] + s[i+1:]
            break
    if s.islower() == True:
        print('AC')
    else:
        print('WA')

### FIXED CODE ###

s = str(input())
if s[0] == 'A' and s[2:-1].count('C') == 1 and (s[1:s.find('C')]+s[s.find('C')+1:]).islower():
    print('AC')
else:
    print('WA')
n = input()
l = []
isz = 0
for i in xrange(n):
    x, y, h = map(int, raw_input().strip().split())
    if h == 0: isz += 1
    l.append([x, y, h])

assert isz != n

ans = [0,0,0]

for cx in xrange(101):
    for cy in xrange(101):
        H = 0
        zH = int(1e18)
        poss = True
        for xyh in l:
            x, y, h = xyh
            tx = abs(cx - x) + abs(cy - y)
            if h != 0:
                nH = tx + h
                if H != 0 and nH != H:
                    poss = False
                    break
                elif H == 0: H = nH
            elif h == 0:
                zH = min(zH, tx + h)
                
        if poss:
            ans = [cx, cy, H]
            break
        
    if poss: break
    
if ans != [0, 0, 0]:
    check = True
    for xyh in l:
        x, y, h = xyh
        tx = abs(cx - x) + abs(cy - y)
        assert h == max(ans[2] - tx, 0)
 
print ans[0], ans[1], ans[2]

### FIXED CODE ###

n = input()
l = []
isz = 0
for i in xrange(n):
    x, y, h = map(int, raw_input().strip().split())
    if h == 0: isz += 1
    l.append([x, y, h])

assert isz != n

ans = [0,0,0]

for cx in xrange(101):
    for cy in xrange(101):
        H = 0
        zH = int(1e18)
        poss = True
        for xyh in l:
            x, y, h = xyh
            tx = abs(cx - x) + abs(cy - y)
            if h != 0:
                nH = tx + h
                if H != 0 and nH != H:
                    poss = False
                    break
                elif H == 0: H = nH
            elif h == 0:
                zH = min(zH, tx)

        if poss:
            if H > zH: poss = False
             
        if poss:
            ans = [cx, cy, H]
            break
        
    if poss: break
    
if ans != [0, 0, 0]:
    check = True
    for xyh in l:
        x, y, h = xyh
        tx = abs(cx - x) + abs(cy - y)
        assert h == max(ans[2] - tx, 0)

print ans[0], ans[1], ans[2]
S=int(input())


for i in range(len(S)):
    A=S[i:i+1]
    print(A)

if S[0:1]==S[1:2]:
    print("Bad")
elif S[1:2]==S[2:3]:
    print("Bad")
elif S[3:4]==S[2:3]:
    print("Bad")
else:
    print("Good")

### FIXED CODE ###


S=input()

if S[0:1]==S[1:2] or S[1:2]==S[2:3] or S[3:4]==S[2:3]:
    print("Bad")
else:
    print("Good")
for _ in range(test_case):
import sys
readline = sys.stdin.readline

N, A, B = map(int, readline().split())

ans = None
if (B - A) % 2 == 0:
    ans = (B-A)//2
else:
    ans = A + (B - A - 1)//2
    ans = min(ans, N-B+1 + (-A+B-1)//2)    
print(ans)
    

### FIXED CODE ###

import sys
readline = sys.stdin.readline

N, A, B = map(int, readline().split())

ans = None
if (B - A) % 2 == 0:
    ans = (B-A)//2
else:
    ans = A + (B - A - 1)//2
    ans = min(ans, N-B+1 + (-A+B-1)//2)    
print(ans)
import re
number=input()
number=number.replace("?",".",100000)
length=len(number)

replica=number
while True:
    if replica[0]==".":
        replica=replica[1:]
    else:
        break
replen=len(replica)

i=0
sumnum=0
while True:
    checknum=str(13*i+5)
    if len(checknum)<replen:
        i+=1
        continue
    checklength=len(checknum)
    if checklength<length:
        while len(checknum)!=length:
            checknum="0"+checknum

    if len(checknum)==length:
        m=re.match(number,checknum)
        if m:
            sumnum+=1
            sumnum=sumnum%1000000007
    
            
    if len(checknum)>length:
        break
    i+=1
    
print(sumnum)

### FIXED CODE ###

#数字はnumberに格納
number=input()
length=len(number)


#調整のための数字
sizemin=1000000007

#まずはからのDPリストを用意
dp=[[0 for i in range(13)] for j in range(length)]

#1桁目の情報を入力
if number[-1]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    dp[0][int(number[-1])]=1

#１０〜９０の、13modリストを作る
modlist=[(i*10)%13 for i in range(10)]


        
#二桁目からの情報を更新していく。
for n in range(length-1):
    #n桁目の情報があれば、次のようにn+1行目を更新。

    #n+1のくらいの数をchecknumとする
    checknum=number[-1*(n+1)-1]
#     print(checknum)

    #n+1の位が整数であれば
    if checknum!="?":
        
        #n[m]の値をn+1[m+(その整数)]にすればいい
        for m in range(13):
            dp[n+1][(m+modlist[int(checknum)])%13]=dp[n][m]
#         print(dp)
        
        
        
        
        
    #n+1のくらいが？の時
    else:
    #？が０〜９までの可能性を全て試す  
    
        for checknum in range(10):
            for m in range(13):
                dp[n+1][(m+modlist[int(checknum)])%13]=(dp[n+1][(m+modlist[int(checknum)])%13]+dp[n][m])%sizemin
#             print(dp)

    #modlistを更新
    modlist=[(j*10)%13 for j in modlist]


print(dp[-1][5])
9
education
7


### FIXED CODE ###

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

for i in range(N):
    if i == K-1:
        continue
    if S[i] != S[K-1]:
        S = S[:i] + '*' + S[i+1:]

print(S)
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR_(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, k = LI()
    a = LI()
    for i in range(k - 1):
        if a[i] > a[i + k]:
            print("No")
        else:
            print("Yes")
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR_(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, k = LI()
    a = LI()
    for i in range(n - k):
        if a[i] >= a[i + k]:
            print("No")
        else:
            print("Yes")
    return


#main
if __name__ == '__main__':
    solve()
#B問題
N,X = map(int,input().split())
L = list(map(int,input().split()))
land = [0]
for i in range(N):
    land.append(land[-1]+L[i])
land.sort()
count = 0
for l in land:
    if land <= X:
        count+=1
        
print(count)

### FIXED CODE ###

#B問題
N,X = map(int,input().split())
L = list(map(int,input().split()))
land = [0]
for i in range(N):
    land.append(land[-1]+L[i])
land.sort()
count = 0
for l in land:
    if l <= X:
        count+=1
        
print(count)
s=input()
t=input()
S=[]
c=0
for i in range(len(s)):
    if s[i] in t:
        c+=1
        p=len(t)-1
        q=t.index(s[i])
      
        if q>i or i-q+p+1>len(s):
            pass
        else:
            s1=s[i-q:i+p-q+1]
           
            count=0
            for j in range(len(s1)):
                
                if s1[j]!=t[j]:
                    count+=1
                else:
                    pass
            S.append(count)
    else:
        pass
if c==0:
    print(len(t))
else:
    print(min(S))

### FIXED CODE ###

S = input()
T = input()

ans = 1000000  # 適当に1001以上を初期値にしておきます

# Tが1文字のときlen(S)回、2文字のときlen(S) - 1回 …… なので、
# len(S) - len(T) + 1 回です
for i in range(len(S) - len(T) + 1):
    score = 0
    U = S[i:i + len(T)]  # Sのi文字目から連続するlen(T)文字を、Uとします
    for j in range(len(T)):
        if U[j] != T[j]:
            score += 1
    ans = min(ans, score)

print(ans)
N,T =map(int,input().split())
t = map(int,input().split())
amount =0


    
for index in range(N-1):
    t_sub = t[index+1]-t[index]
    if t_sub <= T:
        amount+=t_sub
    else:
        amount+=T

        
amount +=T

print(amount)

### FIXED CODE ###

if __name__ == '__main__':
    N, T = map(int, input().split())
    ts = list(map(int, input().split()))
    
    
amount =0


    
for index in range(N-1):
    t_sub = ts[index+1]-ts[index]
    amount+=min(t_sub,T)

        
amount +=T

print(amount)
a, b = list(map(int, input().split()))
if a > b:
    a,b = b,a
if a > c:
    a,c = c,a
if b > c:
    b, c = c, b
print(str(a) + " " + str(b) + " " + str(c))

### FIXED CODE ###

l = list(map(int, input().split()))
l.sort()
for i in range(len(l)):
    if i == len(l)-1:
        print(l[i])
    else:
        print(l[i], end = " ")
n=raw_input()
i=map(raw_input.split())
q=raw_input()
m=map(raw_input.split())
if m == 0
  return true
if i >= n
  return false
res = solve(i + 1, m) || solve(i + 1, m - A[i])
return res

### FIXED CODE ###

n=int(raw_input())
A=map(int, raw_input().split())
q=int(raw_input())
m=map(int, raw_input().split())

def solve(j, m):
  if m == 0:
    return 1
  if j >= n or m > sum(A):
    return 0
  res = solve(j + 1, m) or solve(j + 1, m - A[j])
  return res

for i in range(0,q):
  if solve(0,m[i]):
    print "yes"
  else:
    print "no"
N,W=map(int,input().split())
dp=[[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
	w,v=map(int,input().split())
	for j in range(1,W+1):
		if j-w>=0:
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
		else:
			dp[i][j]=dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

n,*h=map(int,open(0).read().split())
dp=[0]*n
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
	dp[i]=min(dp[i-2]+abs(h[i-2]-h[i]),dp[i-1]+abs(h[i-1]-h[i]))
print(dp[n-1])
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1,np.int64)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])


### FIXED CODE ###

import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))
# dp[i]:価値の総和をちょうどiにできる最小の重さ総和
# dp[i]=w+1となる価値総和iにはできない。
# 求めるのはdp[i]<=wとなる最大のi
dp=np.full(10**5+1,w+1) # ndarray(1000,1000,...,1000])
dp[0]=0
# 10**5:viの総和の最大
for i in range(n):
      w_=wv[i][0]
      v_=wv[i][1]
      # i番目までの商品を取るか取らないかの全ての組み合わせをためすことができる。
      dp[v_:]=np.minimum(dp[v_:], dp[:-v_]+w_)
print(np.where(dp<=w)[0][-1])