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

N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
while m!=[]:
    tmp=max(m)[0]
    m=[l for l in m if l[1]<=tmp]
    p+=1
print(p)

### FIXED CODE ###

N, M = map(int,input().split())
m=[list(map(int, input().split()))[::-1] for _ in range(M)]
m.sort()

b=[]
for i in m:
    if len([tmp for tmp in b if tmp>=i[1]])==0:
        b.append(i[0]-1)
print(len(b))
### BUGGY CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()


#dp = [[0] * (X+1) for _ in range(N+1)]
dp = [None]
dp[0] = [x for x in range(X+1)]


for i, n  in enumerate(numbers):
    dp.append([])
    for x in range(X+1):
        dp[i+1].append(0)
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        dp[i+1][x] += dp[i][x] * i % MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

l %= MOD
ans = 0
for a in A:
  ans += (l * power(a, MOD-2)) % MOD
  ans %= MOD

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

import queue
import sys
input = sys.stdin.readline
def main():
    q = queue.Queue()
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]="0"
                        q.put([i+k[0],j+k[1],1])
    ans=0
    while not q.empty():
        v=q.get()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]="0"
                q.put([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque 
import sys
input = sys.stdin.readline
def main():
    q = deque([])
    h,w=map(int,input().split())
    a=[list(input()) for i in range(h)]
    x=[[-1,0],[1,0],[0,-1],[0,1]]
    for i in range(h):
        for j in range(w):
            if a[i][j]=="#":
                for k in x:
                    if 0<=i+k[0]<h and 0<=j+k[1]<w and a[i+k[0]][j+k[1]]==".":
                        a[i+k[0]][j+k[1]]="0"
                        q.append([i+k[0],j+k[1],1])
    ans=0
    while q:
        v=q.popleft()
        for k in x:
            if 0<=v[0]+k[0]<h and 0<=v[1]+k[1]<w and a[v[0]+k[0]][v[1]+k[1]]==".":
                a[v[0]+k[0]][v[1]+k[1]]="0"
                q.append([v[0]+k[0],v[1]+k[1],v[2]+1])
                ans=v[2]+1
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
s = [int(input()) for i in range(N)]
def dfs(n,count):
    global N,s
    if n == N:
        if count%10==0:
            count = 0
        return count
    return max(dfs(n+1,count),dfs(n+1,count+s[n]))
print(dfs(0,0))

### FIXED CODE ###

N = int(input())
s = []
s_10 = []
for i in range(N):
    x = int(input())
    if x%10 ==0:
        s_10.append(x)
    else:
        s.append(x)
s_10.sort()
s.sort()
if len(s)==0:
    print(0)
    exit()
if sum(s)%10==0:
    print(sum(s)+sum(s_10)-min(s))
else:
    print(sum(s)+sum(s_10))
### BUGGY CODE ###

# 入力
N=int(input())

# 最大回数
c=0

for x in range(1,N+1):
  _c=0
  while True:
    if x%2==0:
      x//=2
      _c+=1
    else:
      c=max(c,_c)

# 出力
print(c)

### FIXED CODE ###

n=int(input())
a=0
c=0
x=0
y=1
for i in range(1,n+1):
  c=0
  a=i
  while True:
    if a%2==0:
      a/=2
      c+=1
    else:
      if x<c:
        x=c
        y=i
      break
print(y)
### BUGGY CODE ###

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

p = []
for i in range(m):
  l,r = map(int, input().split())
  p.append([l,r])
  
s = 0
for i in range(1, n+1):
  t = 0
  for l,r in p:
    if l <= i and i <= r:
      t += 1
    else:
      break
  if t == m:
    s += 1
print(s)

### FIXED CODE ###

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

a = [0]*m
b = [0]*m
for i in range(m):
  l,r = map(int, input().split())
  a[i] = l
  b[i] = r

x = min(b)
y = max(a)
if x >= y:
  print(x-y+1)
else:
  print(0)
### BUGGY CODE ###

#import sys
n, m = map(int, input().split())
s = input()
t = input()

if s[0] != t[0]:
    print(-1)
    exit()
    #sys.exit(0)

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

l = lcm(n, m)
x = [" " for _ in range(l)]

x[0] = s[0]
for i in range(1, n):
    x[(l//n) * i] = s[i]

for i in range(1, m):
    if x[(l//m) * i] == t[i]:
        continue
    if x[(l//m) * i] != " ":
        print(-1)
        exit()
        # sys.exit(0)

print(l)


### FIXED CODE ###

#import sys
n, m = map(int, input().split())
s = input()
t = input()

if s[0] != t[0]:
    print(-1)
    exit()
    #sys.exit(0)

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

l = lcm(n, m)
step = min(l//n, l//m)

for i in range(0, l, step):
    if i % (l//n) == 0 and i % (l//m) == 0:
        if s[i * n // l] != t[i * m // l]:
            print(-1)
            exit()
            # sys.exit(0)

print(l)
### BUGGY CODE ###

N=int(input())
for i in range(1,N+1):
  count=0
  k=i//5+1
  for x in range(k):
    if(x==0):
      continue
    if(x>=21):
      break
    for y in range(x,k):
      if(y==0):
        continue
      if(y>=21):
        break
      for z in range(y,k):
        if(z==0):
          continue
        if(z>=21):
          break
        if((x+y)**2+(y+z)**2+(z+x)**2)//2==i:
          #print(x,y,z)
          #print(i)
          if (x==y and y==z and z==x):
            count+=1
          elif (x!=y and y!=z and z!=x):
            count+=6
          else:
            count+=3
  print(count)

### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = i*i+j*j+k*k+i*j+j*k+k*i;
      if v<10050:
        ans[v]+=1
for i in range(n):
    print(ans[i+1])
### BUGGY CODE ###

import io
import sys


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
4
0
0
0
0
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = []
  for i in range(0, n):
    num = IN_I()
    # print(l, num)
    for j in range(0, len(l) + 1):
      if j == len(l):
        l.append(num)
      else:
        if l[j] < num:
          l[j] = num
          break

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()


### FIXED CODE ###

import io
import sys
from bisect import bisect_right, bisect_left
from collections import deque


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
7
1
0
3
4
1
2
1
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = deque([IN_I()])

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_left(l, num)
    if idx == 0:
      l.appendleft(num)
    else:
      l[idx - 1] = num
    # print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
mx = -10**12
for j in range(1, N):
    for i in range(j):
        mx = max(mx, a[j] - a[i])
print(mx)

### FIXED CODE ###

N = int(input())

#R[0]
minv = int(input())
maxv = -10**12

#R[1..N-1]
for j in range(1, N):
    r = int(input())
    maxv = max(maxv, r - minv)
    minv = min(minv, r)
    
print(maxv)
### BUGGY CODE ###

from collections import Counter
import json
N = int(input())
c = []

for _ in range(N):
    s = input()
    d = dict(Counter(s))
    ds = sorted(d.items(), key=lambda x:x[0])
    c.append(json.dumps(ds))

res = [c.count(e) for e in set(c) if c.count(e) > 1]

sum = 0
for i in res:
    sum += (i*(i-1)//2)


print(sum)


### FIXED CODE ###

from collections import Counter
import json

N = int(input())
ss = []
c = []

for _ in range(N):
    s = input()
    ss.append("".join(sorted(s)))

sum = 0

for i , v in Counter(ss).items():
    sum += (v*(v-1)//2)
print(sum)
### 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(K+1):
  for y in range(K+1):
    if S - x - y <= K and S - x- y >=0:
      cnt+=1
print(cnt)
### BUGGY CODE ###

import bisect

n, q = map(int, input().split())
s = input()
spells = [input().split() for _ in range(q)]

finally_positions = []

for golem_pos in range(-1, n+1):
    for t, d in spells:
        if 0 <= golem_pos < n and s[golem_pos] == t:
            golem_pos += 1 if d == "R" else -1
    finally_positions.append(golem_pos)

left = bisect.bisect_right(finally_positions, -1)
right = bisect.bisect_left(finally_positions, n)

print(right - left)


### FIXED CODE ###

def search_right(a, x, lo=0, hi=None, key=lambda x: x):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < key(a[mid]): hi = mid
        else: lo = mid+1
    return lo


def search_left(a, x, lo=0, hi=None, key=lambda x: x):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if key(a[mid]) < x: lo = mid+1
        else: hi = mid
    return lo


def get_fin_pos(s, td, golem_pos):
    for t, d in td:
        if 0 <= golem_pos < len(s) and s[golem_pos] == t:
            golem_pos += 1 if d == "R" else -1
    return golem_pos


n, q = map(int, input().split())
s = "_{}_".format(input())
spells = [input().split() for _ in range(q)]

left = search_right(range(len(s)), 0, key=lambda golem: get_fin_pos(s, spells, golem))
right = search_left(range(len(s)), len(s) - 1, key=lambda golem: get_fin_pos(s, spells, golem))

print(right - left)
### BUGGY CODE ###

from collections import deque
d = deque()
n = int(input())
for i in range(n):
    s = input().split()
    if str(s[0][0]) == 'i': d.appendleft(int(s[1]))
    elif str(s[0]) =='delete': 
        if int(s[1]) in d:
            d.remove(int(s[1]))
        else: pass
    elif str(s[0][6]) =='F': d.popleft()
    else: 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 ###

import math


def digit_sum(b, n):
    if b > n:
        return n
    else:
        return digit_sum(b=b, n=n // b) + n % b


def main(n, s):
    if s > n:
        return -1
    elif n == s:
        return n + 1
    else:
        b = 2
        while b * b <= n:
            if digit_sum(b, n) == s:
                return b

        p = 1
        b_min = -1
        while p * p <= n:
            if (n - s) % p == 0:
                b = (n - s) // p + 1
                if digit_sum(b, n) == s:
                    b_min = min(b_min, b) if b_min != -1 else b
            p += 1
        return b_min


if __name__ == '__main__':
    N = int(input())
    S = int(input())
    print(main(n=N, s=S))


### FIXED CODE ###

import math


def digit_sum(b, n):
    if b > n:
        return n
    else:
        return digit_sum(b=b, n=n // b) + n % b


def main(n, s):
    if s > n:
        return -1
    elif n == s:
        return n + 1
    else:
        b = 2
        while b * b <= n:
            if digit_sum(b, n) == s:
                return b
            b += 1

        p = 1
        b_min = -1
        while p * p <= n:
            if (n - s) % p == 0:
                b = (n - s) // p + 1
                if digit_sum(b, n) == s:
                    b_min = min(b_min, b) if b_min != -1 else b
            p += 1
        return b_min


if __name__ == '__main__':
    N = int(input())
    S = int(input())
    print(main(n=N, s=S))
### BUGGY CODE ###

a,b,k=map(int,input().split())
R=[i for i in range(a,b+1)]
for x in sorted(set(R[:k])|set(R[-k:])):
    print(x)

### FIXED CODE ###

a,b,k=map(int,input().split())
R=range(a,b+1)
for x in sorted(set(R[:k])|set(R[-k:])):
    print(x)
### BUGGY CODE ###

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

L = []
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            num = S[i]+S[j]+S[k]
            if num not in L:
                L.append(num)
print(len(L))

### FIXED CODE ###

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

y = 0
L = []
for i in range(10):
    for j in range(10):
        L = []
        # print(i,j,k)
        c = str(i)
        p = 0
        l = 0
        while l < N:
            if p == 0 and S[l] == c:
                c = str(j)
                p = 1
            elif p == 1 and S[l] == c:
                p = 2
            elif p == 2 and S[l] not in L:
                L.append(S[l])
            l += 1
        y += len(L)
print(y)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		for _ in range(N):
			if len(q) == 0:
				break
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)


### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)
### BUGGY CODE ###

from sys import exit

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


def get_count():
    count = 1

    considered = []

    for s in S:
        if s not in considered:
            count *= S.count(s) + 1
        considered.append(s)

    count -= 1

    return count


ans = get_count() % (10 ** 9 + 7)

print(ans)


### FIXED CODE ###

from sys import exit

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


def get_count():
    count = 1

    m = {}

    for s in S:
        if s in m.keys():
            m[s] += 1
        else:
            m[s] = 1

    for k in m:
        count *= m[k] + 1

    count -= 1

    return count


ans = get_count() % (10 ** 9 + 7)

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

S=input()
l=len(S)
m=10**9+7
dp=[[0 for _ in range(13)] for _ in range(l)]
if S[-1]=='?':
    dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    dp[0][int(S[-1])]=1
for i in range(1,l):
    if S[-i-1]=='?':
        for j in range(13):
            for k in range(10):
                dp[i][j]+=dp[i-1][(j-k*10**i)%13]%m
    else:
        for j in range(13):
            dp[i][j]=dp[i-1][(j-int(S[-i-1])*10**i)%13]
print(dp[-1][5]%m)

### FIXED CODE ###

S=input()[::-1]
l=len(S)
a=1
m=10**9+7
dp=[1]+[0]*12
for d in S:
    dp2=[0]*13
    if d=='?':
        for j in range(13):
            for k in range(10):
                dp2[(j+k*a)%13]+=dp[j]%m
    else:
        for j in range(13):
            dp2[(j+int(d)*a)%13]=dp[j]
    dp=dp2
    a=(a*10)%13 if a!=1 else 10
print(dp[5]%m)
### BUGGY CODE ###

import numpy as np

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

for i in range(N):
    A_new = A[:i] + A[i+1:]
    A_new_new = np.diff(A_new)
    A_new_new = list(map(lambda n:abs(n), A_new_new))
    ans = abs(A_new[0]) + sum(A_new_new) + abs(A_new[-1])
    print(ans)


### FIXED CODE ###

import numpy as np

N = int(input())
a = list(map(int,input().split()))
dp = [0] * (N+1)
dp[0] = abs(a[0])
for i in range(1, N):
    dp[i] = abs(a[i]-a[i-1])
dp[N] = abs(a[-1])
result = sum(dp)
for i in range(N):
    ans = result
    ans -= dp[i]+dp[i+1]
    if i == 0:
        ans += abs(a[i+1])
    elif i == N-1:
        ans += abs(a[i-1])
    else:
        ans += abs(a[i+1] - a[i-1])
    print(ans)
### BUGGY CODE ###

N = int(input())
S = {}
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N):
    flg = 0
    j  = 0
    while(flg == 0 and j < i):
        if i != j:
#            if len(S[j]) == len(S[i]):
#                if S[j][0] == S[i][0]:
            if S[j] == S[i]:
                S[j] = ''
                ans = ans - 1
                flg = 1
        j = j+1
print(ans)

### FIXED CODE ###

N = int(input())
S = []
ans = N
S = [input() for i in range(N)]
#for i in range(N):
#    S.append(input())
S.sort()
for i in range(N-1):
    if S[i] == S[i+1]:
        ans = ans - 1
print(ans)
### BUGGY CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7
    for i in range(len(s)):
        if s[-i-1] == -1:
            for j in range(10):
                if i == 0:
                    dp[1][j % 13] += 1
                else:
                    for k in range(13):
                        dp[1][(pow(10, i, 13) * j + k) % 13] += (dp[0][k] % mod)
        else:
            if i == 0:
                dp[1][s[-i-1] % 13] += 1
            else:
                for k in range(13):
                    dp[1][(pow(10, i, 13) * s[-i-1] + k) % 13] += (dp[0][k] % mod)
        for j in range(13):
            dp[0][j] = dp[1][j]
            dp[1][j] = 0
    print(dp[0][5] % mod)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    s = [int(v) if v != "?" else -1 for v in list(str(input().rstrip('\n')))]
    dp = [[0] * 13 for _ in range(2)]
    mod = 10 ** 9 + 7

    for i in range(1):
        if s[-i-1] == -1:
            for j in range(10):
                dp[0][j % 13] += 1
        else:
            dp[0][s[-i - 1] % 13] += 1

    for i in range(1, len(s)):
        m = pow(10, i, 13)
        if s[-i-1] == -1:
            for j in range(10):
                mj = m * j
                for k in range(13):
                    dp[1][(mj + k) % 13] += dp[0][k]
        else:
            for k in range(13):
                dp[1][(m * s[-i-1] + k) % 13] += dp[0][k]
        for j in range(13):
            dp[0][j] = dp[1][j] % mod
            dp[1][j] = 0
    print(dp[0][5] % mod)


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

INF = float('inf')
N,W = map(int,input().split())
wv = [list(map(int,input().split())) for _ in range(N)]

dp = [[-INF]*(W+1) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(W+1):
        if j-wv[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j-wv[i][0]]+wv[i][1],dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(max(dp[-1]))

### FIXED CODE ###

N,W = map(int,input().split())
c = [tuple(map(int,input().split())) for i in range(N)]
DP = [[0 for i in range(W+1)] for i in range(N+1)]

for i in range(N):
    for w in range(W+1):
        if w-c[i][0] < 0:
            DP[i+1][w] = DP[i][w]
        else:
            DP[i+1][w] = max(DP[i][w-c[i][0]]+c[i][1],DP[i][w])
print(DP[N][W])
### BUGGY CODE ###

nums = int(input())
ary = list(map(int, input().split()))
parity = [0,0]

# 奇数、偶数の数をとる
for i in ary:
    if   i % 2 == 0:
        parity[0] += 1
    elif i % 2 == 1:
        parity[1] += 1

while not parity[0] + parity[1] == 3:
    if parity[0] >= 2:
        parity[0] -= 2
        parity[0] += 1
    elif parity [1] >= 2:
        parity[1] -= 2
        parity[0] += 1
if (parity[0] == 1 and parity[1] == 2) or (parity[0] == 3 and parity[1] == 0):
    print("YES")
else :print("NO")

### FIXED CODE ###

nums = int(input())
ary = list(map(int, input().split()))
parity = [0,0]

# 奇数、偶数の数をとる
for i in ary:
    if   i % 2 == 0:
        parity[0] += 1
    elif i % 2 == 1:
        parity[1] += 1

while not parity[0] + parity[1] <= 2:
    if parity[0] >= 2:
        parity[0] -= 2
        parity[0] += 1
    elif parity [1] >= 2:
        parity[1] -= 2
        parity[0] += 1
if parity[0] == 2 or parity[1] == 2:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import math
from functools import reduce
def gcd(*numbers):
  return reduce(math.gcd,numbers)
K=int(input())
a=list(range(1,K+1))
b=list(range(1,K+1))
c=list(range(1,K+1))
ans=0
for j in a:
  for k in b:
    for l in c:
      ans+=gcd(j,k,l)
print(ans)

### FIXED CODE ###

import math
K=int(input())
ans=0
for j in range(1,K+1):
  for k in range(1,K+1):
    a=math.gcd(j,k)
    for l in range(1,K+1):
      ans+=math.gcd(a,l)
print(ans)
### BUGGY CODE ###

N=int(input())
A=[]
while N>0:
  A.append(N%10)
  N//=10
a=(sum(A))
if a%9==0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N=int(input())
L=[int(x) for x in list(str(N))]
a=sum(L)
if a%9==0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

import sys
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()

ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)