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

import sys
from collections import defaultdict


def dfs(root, links, in_count):
    topological = []
    q = root.copy()
    while q:
        v = q.pop()
        topological.append(v)
        for u in links[v]:
            in_count[u] -= 1
            if in_count[u] == 0:
                q.add(u)
    return topological


n = int(input())
lines = sys.stdin.readlines()

roots = set()
in_count = defaultdict(lambda: 0)
out_links = defaultdict(set)

for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    j = aaa[0] - 1
    prev = i * n + j if i < j else j * n + i
    roots.add(prev)

    for j in aaa[1:]:
        j -= 1
        key = i * n + j if i < j else j * n + i
        out_links[prev].add(key)
        in_count[key] += 1
        prev = key

roots = {r for r in roots if in_count[r] == 0}

if not roots:
    print(-1)
    exit()

topological = dfs(roots, out_links, in_count)
if len(topological) != n * (n - 1) // 2:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in out_links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))


### FIXED CODE ###

import sys
from collections import defaultdict


def dfs(root, links):
    status = {}
    topological = []
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            q.append((v, 1))
            status[v] = 1
            d += 1
            for u in links[v]:
                if u in status:
                    if status[u] == 1:
                        return False
                else:
                    q.append((u, 0, d))
        else:
            v = node[0]
            status[v] = 2
            topological.append(v)
    topological.reverse()
    return topological


n = int(input())
links = defaultdict(set)
may_root = set()
lines = sys.stdin.readlines()
matches = []
for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    match_order = []
    for j in aaa:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * n + b
        match_order.append(key)
    matches.append(match_order)
    may_root.add(match_order[0])

for i in range(n):
    kkk = matches[i]
    prev = kkk[0]

    for key in kkk[1:]:
        links[prev].add(key)
        may_root.discard(key)
        prev = key

if not may_root:
    print(-1)
    exit()

topological = dfs(may_root, links)
if topological == False:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))
### BUGGY CODE ###

import numpy as np
NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
X=np.ones(NM[0])
n=0
x=0
for i in range(NM[0]):
  if X[i]==0:
    continue
  for j1 in AB:
    for j2 in j1:
      if j2==i+1:
        if j1.index(j2)==0:
          n=j1[1]
        else:
          n=j1[0]
        if H[i]<=H[n-1]:
          X[i]=0
          break
        else:
          X[n-1]=0
    if X[i]==0:
        break
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""

### FIXED CODE ###

import numpy as np
NM = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]
X=np.ones(NM[0])
AB=[]
for i in range(NM[1]):
  AB.append([int(x) for x in input().split()])
  if H[AB[i][0]-1]>H[AB[i][1]-1]:
    X[AB[i][1]-1]=0
  elif H[AB[i][0]-1]<H[AB[i][1]-1]:
    X[AB[i][0]-1]=0
  else:
    X[AB[i][1]-1]=0
    X[AB[i][0]-1]=0
x=0
for i in range(NM[0]):
  if X[i]==1:
    x+=1
print(x)

"""
6 5
8 6 9 1 2 1
1 3
4 2
4 3
4 6
4 6

3
"""
### BUGGY CODE ###

def gcd(x, y, z):
  while y:
    x, y = y, x % y
  while z:
    x, z = z, x % z
  return x

N = int(input())
wa = 0
for i in range (1,N+1):
  for j in range (1,N+1):
    for h in range (1,N+1):
      wa += gcd(i,j,h) 
print(wa)
  
  

### FIXED CODE ###

from math import gcd

"""
def gcd(x, y, z):
  while y:
    x, y = y, x % y
  while z:
    x, z = z, x % z
  return x
"""

N = int(input())
wa = 0
for i in range (1,N+1):
  for j in range (1,N+1):
    for h in range (1,N+1):
      wa += gcd(gcd(i,j),h) 
print(wa)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    b.append(a[i])
    b = b[::-1]

for i in b:
    print(i)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if n % 2:
    li = a[1::2][::-1] + a[::2]
    li = li[::-1]
else:
    li = a[::2][::-1] + a[1::2]
    li = li[::-1]
print(" ".join(map(str, li)))
### BUGGY CODE ###

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

l = [0] * (n + 1)
s = 0

for i in range(m):
    L, R = map(int, input().split())
    for j in range(L, R+1):
        l[j] += 1

for k in range(n + 1):
    if l[k] == m:
        s += 1

print(s)


### FIXED CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
li = []


for _ in range(m - 1):
    l_, r_ = map(int, input().split())
    l = max(l, l_)
    r = min(r, r_)


print(max(r - l + 1, 0))
### BUGGY CODE ###

import math

def primeornot(n):
  i = 2
  flag = 1
  if(n == 1):
    return 0
  while(i <= math.sqrt(n)):
    if(n % i == 0):
      flag = 0
      break
    else:
      i += 1
  return flag
    
Q = int(input())
for i in range(Q):
  l,r = map(int, input().split())
  ans = 0
  for n in range(l, r+1, 2):
    ans += ( primeornot(n) * primeornot((n+1)//2) )
  print(ans)

### FIXED CODE ###

import bisect
Q = int(input())
maxn = 10 ** 5
intn = [True] * (maxn+1)
intn[0] = False
intn[1] = False
prime = list()
like2017 = list()
for n in range(2, maxn+1):
  if(intn[n] == False):
    continue
  prime.append(n)
  tmp = n
  while(tmp <= maxn):
    intn[tmp] = False
    tmp += n

for i in prime:
  q = (i+1)//2
  q_loc = bisect.bisect_left(prime, q)
  if(prime[q_loc] == q):
    like2017.append(i)

for i in range(Q):
  l, r = map(int, input().split())
  ln = bisect.bisect_left(like2017, l)
  rn = bisect.bisect_right(like2017, r)
  print(rn-ln)
### BUGGY CODE ###

n, p = [int(i) for i in input().split()]
num = int(p ** (1 / n)) + 1
for i in range(num):
    pp = p
    dv = num - i
    for j in range(n):
        if pp % dv == 0:
            pp /= dv
        else:
          break
    else:
        ans = dv
        break
print(ans)

### FIXED CODE ###

n, p = [int(i) for i in input().split()]
if n >= 10 ** 4:
    print(1)
    exit()

num = int(p ** (1 / n)) + 1
for i in range(num):
    pp = p
    dv = num - i
    if pp % (dv ** n) == 0:
        ans = dv
        break
print(ans)
### BUGGY CODE ###

#ABC129D-Lamp.py

#import list
from sys import stdin, setrecursionlimit
#from functools import lru_cache
import numpy as np

input = stdin.readline
#setrecursionlimit(1000)

#constant


#variable

#function
#@lru_cache(maxsize=None)

#class

#main function
def main():
    H, W = list(map(int,input().split()))
    S = [input() for _ in range(H)]
    L = np.zeros((H,W))
    R = np.zeros((H,W))
    U = np.zeros((H,W))
    D = np.zeros((H,W))

    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i,j] = 0
            elif S[i][j] == ".":
                if j == 0:
                    L[i,j] = 1
                else:
                    L[i,j] = L[i,j-1] + 1

            if S[i][W-j-1] == "#":
                R[i,W-j-1] = 0
            elif S[i][W-j-1] == ".":
                if j == 0:
                    R[i,W-j-1] = 1
                else:
                    R[i,W-j-1] = R[i,W-j] + 1

            if S[i][j] == "#":
                U[i,j] = 0
            elif S[i][j] == ".":
                if i == 0:
                    U[i,j] = 1
                else:
                    U[i,j] = U[i-1,j] + 1

            if S[H-i-1][j] == "#":
                D[H-i-1,j] = 0
            elif S[H-i-1][j] == ".":
                if i == 0:
                    D[H-i-1,j] = 1
                else:
                    D[H-i-1,j] = D[H-i,j] + 1

    maxScore = 0
    score = np.array([L[i,j]+R[i,j]+U[i,j]+D[i,j]-3 for i in range(H) for j in range(W)])
    print(int(score.max()))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#ABC129D-Lamp.py

#import list
import sys
import numpy as np

#main function
def main():
    buffer = sys.stdin.buffer
    H, W = list(map(int,buffer.readline().split()))
    S = np.frombuffer(buffer.read(H*(W+1)), dtype="B") == ord(".")
    S = S.reshape((H,W+1))[:,:-1]
    L = np.empty((H,W), dtype="i4")
    R = np.empty((H,W), dtype="i4")
    U = np.empty((H,W), dtype="i4")
    D = np.empty((H,W), dtype="i4")

    L[:,0] = S[:,0]
    for i in range(1,W):
        L[:,i] = (L[:,i-1] + 1) * S[:,i]

    R[:,-1] = S[:,-1]
    for i in range(1,W):
        R[:,-1-i] = (R[:,-i] + 1) * S[:,-1-i]

    U[0] = S[0]
    for i in range(1,H):
        U[i] = (U[i-1] + 1) * S[i]

    D[-1] = S[-1]
    for i in range(1,H):
        D[-1-i] = (D[-i] + 1) * S[-1-i]

    score = L + R + U + D - 3
    print(int(score.max()))


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

n = int(input())
p = [float(i) for i in input().split()]

dp = [[0.0 for _ in range(n+1)] for _ in range(n+1)] #dp[i枚投げる 1はじまり][j枚表の確率 1はじまり]

dp[0][0] = 1.0 #0枚投げて0枚表の確率は1

for i in range(n): #i+1枚目を投げる 1はじまり
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1.0 - p[i])

#print(dp)
ans = 0
for i in range(n//2+1, n+1):
    ans += dp[n][i]
print(ans)


### FIXED CODE ###

n = int(input())
p = [float(i) for i in input().split()]

dp = [[0.0 for _ in range(n+1)] for _ in range(n+1)] #dp[i枚投げる 1はじまり][j枚表の確率 1はじまり]

dp[0][0] = 1.0 #0枚投げて0枚表の確率は1

for i in range(n): #i+1枚目を投げる 1はじまり
    for j in range(i+1):
        dp[i+1][j+1] += dp[i][j] * p[i]
        dp[i+1][j] += dp[i][j] * (1.0 - p[i])

#print(dp)
ans = 0
for i in range(n//2+1, n+1):
    ans += dp[n][i]
print(ans)
### BUGGY CODE ###

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

#output
import fractions
import  functools
import numpy as np

mod = 10**9 + 7

gcd = functools.reduce(fractions.gcd, A)

#def lcm_base(x, y):
#    return (x*y) // fractions.gcd(x, y)
#def lcm_list(numbers):
#    return functools.reduce(lcm_base, numbers, 1)

lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i]//fractions.gcd(lcm, A[i])

answer = 0
for i in range(N):
    answer += lcm//A[i] % mod

print(answer % mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
#output
import fractions, functools
 
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)
 
lcm = lcm_list(A)
 
answer = 0
for i in range(N):
    answer += lcm//A[i]
 
print(answer % (10**9 + 7))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

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

ans = 1
for i in range(N):
    B = A[:i] + A[i+1:]
    ans = max(ans, reduce(gcd, B))

print(ans)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

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

L = [reduce(gcd, A[1:])]
l = A[0]
for i in range(N-1):
    l = gcd(l, A[i])
    L.append(l)

R = [reduce(gcd, A[:N-1])]
r = A[-1]
for i in range(N-1, 0, -1):
    r = gcd(r, A[i])
    R.append(r)

ans = 1
for i in range(N):
    ans = max(ans, gcd(L[i], R[-(i+1)]))

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

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
for i in range(N-1):
    x,y = map(int, input().split())
    T[x] += [y]
    T[y] += [x]

DP = [[0] * (N+1) for _ in range(2)]

def dfs(n,oya):

    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD) 



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)
### BUGGY CODE ###

N,M = map(int, input().split())
p = [0]*M
S = [0]*M
for i in range(M):
    p[i],S[i] = input().split()
import numpy as np
p = [int(s) for s in p]
p1 = np.array(p)
S1 = [1 if i=="AC" else 0 for i in S]
N1 = list(set(p1 * S1))


A = 0
B = 0
for i in range(M):
    if p1[i] in N1:
        A += S1[i]
        B += (1-S1[i])
        if S1[i] ==1:
            N1.remove(p1[i])
print(str(A)+" "+str(B))

### FIXED CODE ###

N,M = map(int, input().split())
p = [0]*M
S = [0]*M
for i in range(M):
    p[i],S[i] = input().split()
q = [int(s)-1 for s in p]
X = [0]*N
Y = [0]*N
A = 0
B = 0
for i in range(M):
    if S[i] == "AC":
        if Y[q[i]]==0:
            Y[q[i]]+=1
            A += 1
            B += X[q[i]]
    else:
        if Y[q[i]]==0:
            X[q[i]] += 1
print(str(A)+" "+str(B))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

h,w = map(int,input().split())

matrix = [[1]*(w+2)]
matrix += [[1] + [x == '#' for x in input().rstrip()] + [1] for _ in range(h)]
matrix.append([1]*(w+2))

matrix_list1 = []

cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j]:
            matrix_list1.append((i,j))

while matrix_list1:
    matrix_list2 = []
    for x,y in matrix_list1:
        if not matrix[x+1][y]:
            matrix[x+1][y] = 1
            matrix_list2.append((x+1,y))
        if not matrix[x-1][y]:
            matrix[x-1][y] = 1
            matrix_list2.append((x-1,y))
        if not matrix[x][y+1]:
            matrix[x][y+1] = 1
            matrix_list2.append((x,y+1))
        if not matrix[x][y-1]:
            matrix[x][y-1] = 1
            matrix_list2.append((x,y-1))
    matrix_list1 = matrix_list2
    cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

l,r=map(int,input().split())
m,ans=2019,2018
r=min(r,l+2019*2)
for i in range(l,r+1):
  for j in range(i+1,r+1):
    ans=min(ans,(i*j)%m)
print(ans)


### FIXED CODE ###

l,r=map(int,input().split())
m=2019
if l//m<r//m:
  print(0)
else:
  ans=m
  for i in range(l%m, r%m+1):
    for j in range(i+1,r%m+1):
      ans=min(ans,i%m*j%m)
  print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
b = [[] for i in range(n)]
for i in range(m):
	p, y = map(int, input().split())
	a.append([p,y])
	b[p-1].append(y)

for i in range(n):
	b[i].sort()

for i, j in a:
	x = b[i-1].index(j)
	print ("{:06d}".format(i) + "{:06d}".format(x+1))

### FIXED CODE ###

n, m = map(int, input().split())
a = []
b = [[] for i in range(n)]
for i in range(m):
	p, y = map(int, input().split())
	a.append([p,y])
	b[p-1].append(y)
dic = {}
for i in range(n):
	b[i].sort()
	for j,k in enumerate(b[i]):
		dic[k] = j+1

for i, j in a:
	print ("{:06d}".format(i) + "{:06d}".format(dic[j]))
### BUGGY CODE ###

#!/usr/bin/env python

l_s = []
c = 0
n = int(input())
for i in range(n):
    s = input()
    l_s.append(sorted(s))

for i in range(len(l_s)):
    c += l_s[i:].count(l_s[i])-1

print(c)

### FIXED CODE ###

#!/usr/bin/env python
import math

l_s = set()
c = 0
n = int(input())
dup = {}

for i in range(n):
    st = sorted(input())
    s  = "".join(st)
    if s in l_s:
        if s in dup.keys():
            dup[s] += 1
        else:
            dup[s] = 1
        c += dup[s]
    l_s.add(s)

print(c)
### BUGGY CODE ###

def resolve():
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    for i in range(n):
        if i+1 not in A:
            Route[i+1] = (Route[i] + Route[i+1]) % (10**9 + 7)
            #Route[i+1] %= 10**9 + 7
        if i+2 not in A and i+2 <= n:
            Route[i+2] = (Route[i] + Route[i+2]) % (10**9 + 7)
            #Route[i+2] %= 10**9 + 7

    print(Route[n])
resolve()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    is_safe = [True] * (N+2)
    for a in A:
        is_safe[a+1] = False

    dp = [0] * (N+2)
    dp[1] = 1
    for i in range(2, N+2):
        if is_safe[i]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0

    return dp[N+1]


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

from collections import defaultdict
from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

Count = [sum(c == '1' for c in s) for s in S]
total = sum(Count)

while 0 in Count:
  i = Count.index(0)
  del S[i]
  del Count[i]
H = len(S)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    DS = defaultdict(list)
    i = 0
    for j, s in enumerate(S):
      if j > 0 and X[j-1]:
        i += 1
      DS[i].append(s)
    ans = sum(X)
    DC = defaultdict(int)
    for j in range(W):
      if any(DC[k] + sum(s[j] == '1' for s in s_list) > K for k, s_list in DS.items()):
        ans += 1
        DC = defaultdict(int)
      for k, s_list in DS.items():
        DC[k] += sum(s[j] == '1' for s in s_list)
    answer = min(answer, ans)

print(answer)

### FIXED CODE ###

from collections import defaultdict
from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)

C = [[int(s[i]) for s in S] for i in range(W)]

total = sum(sum(c) for c in C)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)
### BUGGY CODE ###

S = input()
S = list(S)
S.reverse()
T = []
n = len(S)
for i in range(n):
  T.append(S[i])
  mojiretu = ''.join(T)
  if mojiretu == "maerd" or mojiretu == "remaerd" or mojiretu == "esare" or mojiretu == "resare":
    T =[]

N = len(T)
if N == 0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

S = input()
S = list(S)
S.reverse()
T = []
n = len(S)
for i in range(n):
  T.append(S[i])
  mojiretu = ''.join(T)
  m = len(mojiretu)
  if mojiretu == "maerd" or mojiretu == "remaerd" or mojiretu == "esare" or mojiretu == "resare":
    T =[]
  elif m==8:
      break
N = len(T)
if N == 0:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

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

DP = {0: 0}
for i in range(N):
    wi, vi = map(int, input().split())
    p = {}
    for j in DP:
        if j+wi <= W and DP.get(j+wi, 0) < DP[j]+vi:
            p[j+wi] = DP[j]+vi
    for pi in p:
        DP[pi] = p[pi]
print(max((DP[x] for x in DP)))


### FIXED CODE ###

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

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

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

print(DP[0])
### BUGGY CODE ###

def kitaichi(x):
    return x * (x+1) / (2 * x)

def main():
    n, k = map(int, input().split())
    inlis = tuple(map(int, input().split()))

    tmp = 0
    for i in range(n - k + 1):
        if tmp < sum(inlis[i:i+k]):
            tmp = sum(inlis[i:i+k])
            tmplis = inlis[i:i+k]
    ans = sum(map(kitaichi, tmplis))
    print(ans)



    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def kitaichi(x):
    return x * (x+1) / (2 * x)

def main():
    n, k = map(int, input().split())
    inlis = tuple(map(int, input().split()))
    kitalis = list(map(kitaichi, inlis))
    kitadic = {}
    kitadic[0] = kitalis[0] 
    for i in range(1, n):
        kitadic[i] = kitadic[i-1] + kitalis[i]
       
    tmp = 0
    if n == k:
        print(kitadic[n-1])
    else:
        for i in range(n - k):
            atai = kitadic[i+k] - kitadic[i]
            if tmp < atai:
                tmp = atai
        print(tmp)
        exit()



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

n = int(input())
S = input()
patterns = ["RGB","RBG","GBR","GRB","BRG","BGR"]

ans = 0
for pattern in patterns:
    c1 = pattern[0]
    c2 = pattern[1]
    c3 = pattern[2]
    cands = []
    #i c1の位置で
    for i1 in range(n):
        for i2 in range(i1 + 1,n):
            if S[i1] == c2 and S[i2] == c3:
                cands.append((i1,i2-i1))
    # anss[i1][i2-i1]→左をi1に固定したときの、距離i2-i1の組の個数

    for  i in range(0,n):
        if S[i] == c1:
            for cand in cands:
                if  cand[0] - i  != cand[1] and cand[0] > i:
                    ans += 1

print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()
patterns = ["RGB","RBG","GBR","GRB","BRG","BGR"]
acc  = [ [0] * (n + 1) for _ in range(n+1)]

ans = 0
for pattern in patterns:
    c1 = pattern[0]
    c2 = pattern[1]
    c3 = pattern[2]
    cands = []
    #i c1の位置で
    for i1 in range(n):
        for i2 in range(i1 + 1,n):
            if S[i1] == c2 and S[i2] == c3:
                cands.append((i1,i2-i1))
    # anss[i1][i2-i1]→左をi1に固定したときの、距離i2-i1の組の個数
    cands.reverse()
    di = defaultdict(lambda :set())
    for cand in cands:
        left,dist = cand
        di[left].add(dist)
    acc = [0]
    for i in range(1,n):
        acc.append(acc[i-1] + len(di[i]))

    for  i in range(0,n):
        if S[i] == c1:
            ans += acc[n - 1] -acc[i]
            for i2 in range(i + 1,n):
                if i2 - i in di[i2]:
                    ans -=1
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
arr = [[x, y, z] for x in range(k+1) for y in range(k+1) for z in range(k+1) if x+y+z == s]
print(len(arr))

### FIXED CODE ###

k, s = map(int, input().split())
arr = [1 for x in range(k+1) for y in range(k+1) if k >= s-x-y >= 0]
print(sum(arr))