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

def main():
    h, n = list(map(int, input().split()))
    A, B = [], []
    for _ in range(n):
        a, b = list(map(int, input().split()))
        A.append(a)
        B.append(b)
    mx = max(A)
    mn = min(A)
    INF = float('inf')
    dp = [INF] * (h + mx + 1)
    dp[0] = 0
    for i in range(1, h + mx + 1):
        res = []
        for a, b in zip(A, B):
            if i - a < 0:
                res.append(b)
            else:
                res.append(dp[i - a] + b)
        dp[i] = min(res)
    print(min(dp[h:h + mx + 1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, n = list(map(int, input().split()))
    A, B = [], []
    for _ in range(n):
        a, b = list(map(int, input().split()))
        A.append(a)
        B.append(b)
    mx = max(A)
    INF = float('inf')
    dp = [INF] * (h + mx + 1)
    dp[0] = 0
    for i in range(1, h + mx + 1):
        for a, b in zip(A, B):
            if i - a < 0:
                dp[i] = min(dp[i], b)
            else:
                dp[i] = min(dp[i], dp[i - a] + b)
    print(min(dp[h:h + mx + 1]))


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

n = int(input())
list = list(map(int,input().split()))
di = {}
for i in range(n):
	k = list[i]
	if k not in di:
		di[k]=1
	else:
		di[k]+=1
list_del=[]
for key in di.keys():
	if di[key]==1:
		list_del.append(key)
for i in range(len(list_del)):
	di.pop(list_del[i])
	

for i in range(n):
	k = list[i]
	if k in di:
		di[k]-=1
	co = 0
	for valu in di.values():
		co += valu*(valu-1)/2
	print(int(co))
	
	if k in di:
		di[k]+=1
	



### FIXED CODE ###

n = int(input())
list = list(map(int,input().split()))
di = {}
for i in range(n):
	k = list[i]
	if k not in di:
		di[k]=1
	else:
		di[k]+=1
"""
list_del=[]
for key in di.keys():
	if di[key]==1:
		list_del.append(key)
for i in range(len(list_del)):
	di.pop(list_del[i])
"""
	
su=0
for valu in di.values():
	su += valu*(valu-1)/2
	
for i in range(n):
	k = list[i]
	l = di[k]
	su_ch = su
	su_ch -= l*(l-1)/2
	su_ch += (l-1)*(l-2)/2
	print(int(su_ch))
### BUGGY CODE ###

K, S = map(int, input().split())
cnt = 0
for X in range(K + 1):
    for Y in range(K + 1):
        for Z in range(K + 1):
            if X + Y + Z == S:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int,input().split())
cnt = 0
for X in range(0, K + 1):
    for Y in range(0, K + 1):
        if 0 <= S - X - Y <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

A =[]
c = 0
for i in range(int(input())):
    a=sorted(input())
    c += A.count(a)
    A.append(a)
print(c)

### FIXED CODE ###

A ={}
c = 0
for i in range(int(input())):
    a = str(sorted(input()))
    if a in A:
        A[a] += 1
        c += A[a]
    else:
        A[a] = 0
print(c)
### BUGGY CODE ###

import numpy as np

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

points = np.array([K for _ in range(N)])
yes_no = ['Yes' for _ in range(N)]

for q in range(Q):
    A = int(input()) - 1
    points -= 1
    points[A] += 1

[print('Yes') if p > 0 else print('No') for p in points]

### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

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

points = np.array([K - Q for _ in range(N)])

for q in range(Q):
    A = int(input()) - 1
    points[A] +=1

for p in points:
    if p < 1:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
gcd_v = {}
def gcd(numbers):
    tuple_n = tuple(sorted(numbers))
    try:
        return gcd_v[tuple_n]
    except:
        gcd_v[tuple_n] = reduce(math.gcd, numbers)
        return gcd_v[tuple_n]

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += gcd([a, b, c])

print(ans)


### FIXED CODE ###

import math
from functools import reduce

K = int(input())
def gcd(numbers):
        res = reduce(math.gcd, numbers)
        n = len(set(numbers))
        if n == 1:
            return res
        elif n == 2:
            return res * 3
        else:
            return res * 6

ans = 0
for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            ans += gcd([a, b, c])

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

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i)
NUMIND=[0]*(N+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM[1:]:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

### FIXED CODE ###

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

r = 0
count = 0
r_max = N // R

while r <= r_max:

    g_max = (N-r*R)//G
    g = 0
    while N-r*R-g*G >= 0:
        b = (N-r*R-g*G)/B
        if b.is_integer() and b >= 0:
            count += 1

        g += 1
    
    r += 1

print(count)


### FIXED CODE ###

R,G,B,N = map(int,input().split())

count = 0
for r in range(0,N+1,R):
    for g in range(r,N+1,G):
        b = (N-g)/B
        if b.is_integer() and b >= 0:
            count += 1

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

import collections
N = int(input())
A = []
for i in range(N):
  A.append(input())
a = collections.Counter(A)
ret = [letter for letter,count in a.most_common() if count == a.most_common()[0][1]]
ret.sort()
for r in ret:
  print(r)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
  s = input()
  if s in d.keys():
    d[s] += 1
  else:
    d[s] = 1
mx = 0
for i in d.values():
  mx = max(mx, i)
for i in sorted(d.items()):
  if i[1] == mx:
    print(i[0])
### BUGGY CODE ###

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

ans = 10**11

for i in range(n):
    if abs(sum(A[:i]) - sum(A[i:])) < ans:
        ans = abs(sum(A[:i]) - sum(A[i:]))

print(ans)


### FIXED CODE ###

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

ans = 10**11
sum_A = sum(A)
l = 0

for a in A:
    l += a
    if abs(l - (sum_A - l)) < ans:
        ans = abs(l - (sum_A - l))

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

from fractions import Fraction
from math import ceil, floor

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

def isOk(x):
    cnt = 0
    for a in A:
        cnt += floor(Fraction(a, x))
    return cnt <= K

ok = max(A)
ng = 0
for _ in range(100):
    mid = Fraction(ok + ng, 2)
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ceil(ok))


### FIXED CODE ###

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

def isOk(x):
    cnt = 0
    for a in A:
        cnt += (a - 1) // x
    return cnt <= K

ok = max(A)
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():
    N = in_n()
    X = in_s()
    tx = int(X, 2)

    ans = [0] * N

    one_count = [X.count('1')] * N
    for i in range(N):
        if X[i] == '0':
            one_count[i] += 1
        else:
            one_count[i] -= 1

    t = 1 << N - 1
    for i in range(N):
        a = tx ^ t
        count = 0
        while a:
            if count == 0:
                a = a % one_count[i]
            else:
                a = a % bin(a).count('1')
            count += 1
        ans[i] = count
        t = t >> 1

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    N = int(readline())
    X = readline().rstrip().decode('utf-8')
    nx = int(X, 2)

    ans = [0] * N

    oc = X.count('1')

    if oc - 1 != 0:
        mx = nx % (oc - 1)
        f = True
    else:
        f = False

    px = nx % (oc + 1)

    for i in range(N):

        if X[i] == '0':
            a = (px + pow(2, N - i - 1, oc + 1)) % (oc + 1)
        elif f:
            a = (mx - pow(2, N - i - 1, oc - 1)) % (oc - 1)
        else:
            ans[i] = 0
            continue

        count = 1
        while a:
            a = a % bin(a).count('1')
            count += 1

        ans[i] = count

    print('\n'.join(map(str, ans)))


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


import math
import bisect


prime = [2,3,5,7,11,13,17,19]
for i in range(prime[-1]+2,100000,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)

# print(prime)
#import matplotlib.pyplot as plt
#plt.plot(prime[0:100])
#plt.show()

for i in range(len(prime)):
    if 2*i< prime[i]:
       continue

#    if prime[i] <i+1:
#        continue

    print(prime[i])



q = int(input())

for _ in range(q):

    l, r = map(int,input().split())
 #   l += 1 if l%2 == 0 else 0

#    print((l,r))

    ans = 0
    for i in range( l , r+1, 2):

        xi = bisect.bisect_right(prime, i)
        #print(xi)
        p1 = prime[xi-1]
        if p1 != i:
            continue

        i2 = (i+1)//2
        yi = bisect.bisect_right(prime, i2,lo = (xi+1)//2, hi = xi )
        if prime[yi-1] != i2:
            continue

        ans += 1

    print(ans)

### FIXED CODE ###


import math
import bisect


prime = [2]

tab = [False]*100001
tab[2] = True
for i in range(3,100000+1,2):

    x = int( math.sqrt(i) )
    x += 1 if x%2 == 0 else 0

    found = False
    for p in prime:
        if x < p:
            break;

        if i % p == 0:
            found = True
            break
                
    if not found:
        prime.append(i)
        tab[i] = True

#print(prime[0:10])
#print(tab[0:10])
q = int(input())

ac = [0] * len(tab)

for i in range(1,len(ac)):
    ac[i] = ac[i-1] + (1 if tab[i] and tab[(i+1)//2] else 0)

#print(ac)
for _ in range(q):

    l, r = map(int,input().split())
    
    ans = ac[r] - ac[l-1]

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

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

goukei = 0
for i in range(N):
    for j in range(N):
        if i<j:
            goukei = goukei + A[i] * A[j]
k = 10**9 + 7
print(goukei%k)


### FIXED CODE ###

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

sumA = sum(A)
for i in range(N):
    a = A[i]
    sumA = sumA - a
    goukei = goukei + sumA*a

k = 10**9 + 7
print(goukei%k)
### BUGGY CODE ###

n,k = (int(x) for x in input().split())
ln = list(map(float, input().split()))
ln_mean=[1+0.5*(x-1) for x in ln]
#print(ln_mean)

lnk = [0]*(n - k + 1)
for i in range(n - k + 1):
  tmp_lnk = ln_mean[i:i+k]
  lnk[i] = sum(tmp_lnk)

print(max(lnk))

### FIXED CODE ###

n,k = (int(x) for x in input().split())
ln = list(map(float, input().split()))
ln_mean=[1+0.5*(x-1) for x in ln]
#print(ln_mean)

if n == k:
  print(sum(ln_mean))
else:
  lnk = [0]*(n-k+1)
  m_in = 0
  for i in range(k):
    m_in += ln_mean[i]
  m_max = m_in
  tmp_max = m_in
  for i in range(n-k):
    tmp_max = tmp_max - ln_mean[i] + ln_mean[i+k]
    if m_max < tmp_max:
      m_max = tmp_max
  print(m_max)
### BUGGY CODE ###


def YesNo(b):
    print("Yes" if b else "No")


def solve(v, l, ini):
    ml = 8000*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+8000] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+8000]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [], []
    for i in range(len(f)):
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    YesNo(solve(x, xl, [si]) and solve(y, yl[1:], [-yl[0], yl[0]]))


### FIXED CODE ###


def YesNo(b):
    print("Yes" if b else "No")


def solve(v, l, ini):
    ml = 8000*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+8000] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+8000]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [0], [0]
    for i in range(len(f)):
        if len(f[i]) == 0:
            continue
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    YesNo(solve(x, xl, [si]) and solve(y, yl[1:], [-yl[0], yl[0]]))
### BUGGY CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
for i in range(len(a)):
    m+=a[i]
    s.append(abs(sum(a)-m*2))
    if min(s)<s[i]:
        break
print(min(s))

### FIXED CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
suma=sum(a)
for i in range(len(a)):
    m+=a[i]
    s.append(abs(suma-m*2))
print(min(s))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = min(table[dx][dy], table[x][y])
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = min(table[dx][dy], table[x][y]+1)

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
maze = [input() for i in range(H)]

queue = deque()
queue.append((Ch-1, Cw-1, 0))
inf = float("inf")
table = [[inf] * W for i in range(H)]
table[Ch-1][Cw-1] = 0
walk_move = ((-1, 0), (0, -1), (1, 0), (0, 1))
magic_move = []
for i in range(-2, 3):
  for j in range(-2, 3):
    if not i and not j:
      continue
    else:
      magic_move.append([i, j])

while queue:
  x, y, cost = queue.popleft()
  for i,j in walk_move:
    dx = x+i
    dy = y+j
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost:
      queue.appendleft((dx, dy, cost))
      table[dx][dy] = cost
  for k,l in magic_move:
    dx = x+k
    dy = y+l
    if 0 <= dx <= H-1 and 0 <= dy <= W-1 and maze[dx][dy] == "." and table[dx][dy] > cost+1:
      queue.append((dx, dy, cost+1))
      table[dx][dy] = cost+1

ans = table[Dh-1][Dw-1]
if ans == inf:
  print("-1")
else:
  print(table[Dh-1][Dw-1])
### BUGGY CODE ###

def main():
    #1:初期化
    s = input()
    t = input()
    limit = 7
    dp = [[0]*(len(t)+1) for _ in range(len(s)+1)]

    #2:初期値(いらない)

    #3:dp実行部(貰うDP)or(配るDP)
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i]==t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

    #4:出力
    #print(*dp,sep="\n")
    res = ""
    s_len = len(s)
    t_len = len(t)
    while s_len > 0 and t_len > 0:
        if dp[s_len][t_len] == dp[s_len-1][t_len]:
            s_len -= 1
        elif dp[s_len][t_len] == dp[s_len][t_len-1]:
            t_len -= 1
        else:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)
        

if __name__ == '__main__':
    main()

### FIXED CODE ###

"""memo
    いつものように，numpyを使いたくなかったので他人のコードを参考にした．
    enumerateは「https://note.nkmk.me/python-enumerate-start/」を参考．
"""

def main2():
    #1:初期化
    s = input()
    t = input()
    v = [0] * (len(t) + 1)
    dp = [v]
    #print(v)
    #print(dp)

    #2:初期値(いらない)

    #3:dp実行部(貰うDP)
    for str1 in s:
        v = v.copy()
        #print(i, str1, u, v)
        dp.append(v)
        #print("in",*dp,sep="\n")
        ll, ul = 0, 0
        for j, str2 in enumerate(t, 1):
            uu = v[j]
            if str1 == str2:
                v[j] = ll = ul + 1
            else:
                if ll > uu:
                    v[j] = ll
                else:
                    ll = uu
            ul = uu
        #print("out",*dp,sep="\n")
            
    # #4:出力
    #print(*dp,sep="\n")
    res = ""
    s_len = len(s)
    t_len = len(t)
    while s_len > 0 and t_len > 0:
        if dp[s_len][t_len] == dp[s_len-1][t_len]:
            s_len -= 1
        elif dp[s_len][t_len] == dp[s_len][t_len-1]:
            t_len -= 1
        else:
            res = s[s_len-1] + res
            s_len -= 1
            t_len -= 1
    print(res)

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

N=int(input())
H=list(map(int,input().split()))
L=[0 for _ in range(N)]
for t in range(N):
    if max(L)>N-t:
        break
    for i in range(t,N):
        if t==i:
            continue
        if H[t]>=H[i]:
            L[t]+=1
            H[t]=H[i]
        else:
            break
print(max(L))

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
min=H[0]
count=[0 for _ in range(N)]
cnt=0
t=0
for i in range(1,N):
    if H[i]<=min:
        min=H[i]
        cnt+=1
    else:
        count[t]=cnt
        cnt=0
        t+=1
        min=H[i]
count[t]=cnt
print(max(count))
### BUGGY CODE ###

N, W = map(int, input().split())
V = N * 1000
w, v = [0]*N, [0]*N
for i in range(N):
  w[i], v[i] = map(int, input().split())

dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  for v_sum in range(V+1):
    if v_sum >= v[i-1]:
      dp[i][v_sum] = min(dp[i-1][v_sum - v[i-1]] + w[i-1], dp[i-1][v_sum])
    else:
      dp[i][v_sum] = dp[i-1][v_sum]

ans = 0
for v_sum in range(V+1):
  if dp[N][v_sum] <= W:
    ans = v_sum
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
V = N * 1000
w, v = [0]*N, [0]*N
for i in range(N):
  w[i], v[i] = map(int, input().split())

dp = [[float("INF")]*(V+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
  for v_sum in range(V+1):
    if v_sum >= v[i-1]:
      dp[i][v_sum] = min(dp[i-1][v_sum - v[i-1]] + w[i-1], dp[i-1][v_sum])
    else:
      dp[i][v_sum] = dp[i-1][v_sum]

ans = 0
for v_sum in range(V+1):
  if dp[N][v_sum] <= W:
    ans = v_sum
print(ans)