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

h, w, m = map(int, input().split())
mapa = {}
strings = [0]*h
rows = [0]*w
for i in range(m):
    h1, w1 = map(int, input().split())
    if not mapa.get(h1-1, 0):
        mapa[h1-1] = []
    mapa[h1-1].append(w1-1)
    strings[h1-1] += 1
    rows[w1-1] += 1
maxs = max(strings)
maxr = max(rows)
summa = maxs + maxr - 1
fl = True
for i in range(h):
    if fl and strings[i] == maxs:
        for j in range(w):
            if rows[j] == maxr:
                if j not in mapa.get(i, []):
                    summa = maxs + maxr
                    fl = False
                    break
print(summa)


### FIXED CODE ###

def main():
    h, w, m = map(int, input().split())
    mapa = {}
    strings = [0]*h
    rows = [0]*w
    for _ in range(m):
        h1, w1 = map(int, input().split())
        if not mapa.get(h1-1, 0):
            mapa[h1-1] = []
        mapa[h1-1].append(w1-1)
        strings[h1-1] += 1
        rows[w1-1] += 1
    
    max_s = max(strings)
    max_r = max(rows)
    strings_max = []
    rows_max = []
    for i in range(h):
        if strings[i] == max_s:
            strings_max.append(i)
    for i in range(w):
        if rows[i] == max_r:
            rows_max.append(i)
    
    forbidden_positions = set(mapa[strings_max[0]])
    for item in strings_max[1:]:
        forbidden_positions.intersection_update(set(mapa[item]))

    answer_set = set(rows_max).difference(forbidden_positions)
    if answer_set:
        print(max_s + max_r)
    else:
        print(max_s + max_r - 1)

main()
### BUGGY CODE ###

N,M = map(int,input().split())
a = list(int(input()) for i in range(M))
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
if 1 in a:
    dp[1] = 0
for i in range(2,N+1):
    if i in a:
        continue
    
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
ans = dp[N]
print(ans)



### FIXED CODE ###

N,M = map(int,input().split())
a = set([int(input()) for i in range(M)])
dp = [0]*(N+1)
dp[0] = 1
dp[1] = 1
if 1 in a:
    dp[1] = 0
for i in range(2,N+1):
    if i in a:
        continue
    
    dp[i] = (dp[i-2]+dp[i-1])%1000000007
ans = dp[N]
print(ans)
### BUGGY CODE ###

def equalCheck(aList, bList):
  checkList = [0] * 10
  for i in range(10):
    for j in range(10):
      if aList[i] == bList[j] and checkList[j] == 0:
        checkList[j] = 1
  if 0 in checkList:
    return False
  return True

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

count = 0
for i in range(N):
  for j in range(i+1,N):
    if equalCheck(strList[i], strList[j]):
      count += 1
      
print(count)





### FIXED CODE ###

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

count = 0

dict = {}

for i in range(N):
  charList = list(strList[i])
  charList.sort()
  key = "".join(charList)
  if not key in dict:
    dict[key] = 1
  else:
    dict[key] += 1  

# dictが持つvalue値を要素にfor文で回す
count = 0;
for v in dict.values():
  count += (v * (v-1) // 2)
print(count)
### BUGGY CODE ###

s = input()
l = len(s)
r = 0
m = [0]*2019
for i in range(3,l):
    num = int(s[i])
    m2 = [0]*2019
    for j in range(1,2019):
        j2 = (j*10+num) % 2019
        m2[j2] += m[j]
    m2[int(s[i-3:i+1]) % 2019] += 1
    r += m2[0]
    m2[0] = 0
    m = m2.copy()
print(r)

### FIXED CODE ###

s = input()
s_r = s[::-1]
lmod = [0]
cmod = 0
for n,i in enumerate(s_r):
    cmod += int(i)*pow(10,n,2019) % 2019
    cmod = cmod % 2019
    lmod.append(cmod)

from collections import Counter
r = 0
for _,i in Counter(lmod).items():
    r += i*(i-1)/2

print(int(r))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
N,M=map(int,input().split())
A=list(map(int,input().split()))
queue=deque(A)
for i in range(M):
    queue.append(max(queue)//2)
    queue.remove(max(queue))
print(sum(queue))

### FIXED CODE ###

from heapq import heappop,heappush,heapify
n,m=map(int,input().split())
A=list(map(int,input().split()))
A_m=list(map(lambda x: -x,A))
heapify(A_m)
pop=lambda: -heappop(A_m)
push=lambda x: heappush(A_m,-x)
for _ in range(m):
    x=pop()
    push(x//2)
print(-sum(A_m))
### BUGGY CODE ###

X = input()
while 'ST' in X:
    X.replace('ST', '')
print(len(X))

### FIXED CODE ###

X = input()
t = 0
s = 0
for i in X:
    if i == 'T':
        if s > 0:
            s -= 1
        else:
            t += 1
    if i == 'S':
        s += 1
print(s + t)
### BUGGY CODE ###

n=int(input())
r=list(map(int,input().split()))
m=int(input())
d=list(map(int,input().split()))

for item in d:
  if item in r:
    r.remove(item)
  else:
    print("NO")
    exit()
print("YES")

### FIXED CODE ###

import collections

a=int(input())
b=collections.Counter(list(map(int,input().split())))
c=int(input())
d=collections.Counter(list(map(int,input().split())))
e=set(d)

for item in e:
  if d[item]>b[item]:
    print("NO")
    exit()
    
print("YES")
### BUGGY CODE ###

import sys

n, k = [int(x) for x in input().split(" ")]
h_list = [int(x) for x in input().split(" ")]

dp = [sys.maxsize] * len(h_list)
dp[0] = 0
dp[1] = abs(h_list[1] - h_list[0])

for i in range(2, len(dp)):
  dp_i_costs = []
  for j in range(k+1):
    if i - j >= 0:
      dp_i_costs.append(dp[i - j] + abs(h_list[i] - h_list[i - j]))
  
  dp[i] = min(dp_i_costs)

print(dp[-1])

### FIXED CODE ###

import sys

n, k = [int(x) for x in input().split(" ")]
h_list = [int(x) for x in input().split(" ")]

dp = [sys.maxsize] * len(h_list)
dp[0] = 0
dp[1] = abs(h_list[1] - h_list[0])

for i in range(2, len(dp)):
  dp_i_costs = []
  for j in range(k+1):
    if i - j >= 0:
      dp_i_costs.append(dp[i - j] + abs(h_list[i] - h_list[i - j]))
  
  dp[i] = min(dp_i_costs)

print(dp[-1])
### BUGGY CODE ###

N,M =map(int,input().split())
sta = M//N
for i in range(0,sta):
    i = sta-i
    if M%i==0:
        print(i)
        break


### FIXED CODE ###

N,M =[int(i)for i in input().split()]
l=[]
for i in range(1,int(M**0.5+2)):
    if M%i==0:
        if M/i >= N:
            l.append(i)
        if i >= N:
            l.append(M/i)
print(int(max(l)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+2**i,x+1)

    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0)%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+(1<<i),x+1)

    ANS%=mod
    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
types = {}
for i in A: types[i] = types.get(i, 0) + 1
A = sorted([types[k] for k in types], reverse=True)
L = len(A)
cumsum = [0 for i in range(L+1)]
for i in range(L-1, -1, -1):
    cumsum[i] = A[i] + cumsum[i+1]

# Highest K for given O
def calc(O):
    def getMidPoint(lo, hi):
        if lo >= hi: return lo
        mid = lo + (hi - lo+1) // 2
        if A[mid] > O:
            return getMidPoint(mid, hi)
        else:
            return getMidPoint(lo, mid-1)

    mid = getMidPoint(0, L-1)
    if A[mid] < O: mid = - 1
    return (mid+1) + cumsum[mid+1] // O

for K in range(1, N+1):
    def getO(lo, hi):
        if lo >= hi: return lo
        mid = lo + (hi - lo+1) // 2
        if calc(mid) < K:
            return getO(lo, mid - 1)
        else:
            return getO(mid, hi)
        
    print(getO(0, N))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
types = {}
for i in A: types[i] = types.get(i, 0) + 1
A = sorted([types[k] for k in types], reverse=True)
L = len(A)
cumsum = [0 for i in range(L+1)]
for i in range(L-1, -1, -1):
    cumsum[i] = A[i] + cumsum[i+1]



def getMidPoint(lo, hi, O):
    if lo >= hi: return lo
    mid = lo + (hi - lo+1) // 2
    if A[mid] > O:
        return getMidPoint(mid, hi, O)
    else:
        return getMidPoint(lo, mid-1, O)

getMid = [getMidPoint(0, L - 1, o) for o in range(N+1)]

# Highest K for given O
def calc(O):
    

    mid = getMid[O]
    if A[mid] < O: mid = - 1
    return (mid+1) + cumsum[mid+1] // O

for K in range(1, N+1):
    def getO(lo, hi):
        if lo >= hi: return lo
        mid = lo + (hi - lo+1) // 2
        if calc(mid) < K:
            return getO(lo, mid - 1)
        else:
            return getO(mid, hi)
        
    print(getO(0, N))
### BUGGY CODE ###

n = int(input())
hantei_list = [1 for _ in range(n)]
moji_list = [str(input()) for _ in range(n)]

sosuu = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

for i in range(n):
  for j in range(10):
    hantei_list[i] *= sosuu[ord(moji_list[i][j])-ord('a')]

counter = 0
for i in range(n):
  for j in range(i+1, n):
    if hantei_list[i] == hantei_list[j]:
      counter += 1
print(counter)

### FIXED CODE ###

n = int(input())
hantei_list = [1 for _ in range(n)]
moji_list = [str(input()) for _ in range(n)]
prime_number = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
for i in range(n):
  for j in range(10):
    hantei_list[i] *= prime_number[ord(moji_list[i][j])- ord('a')]

# unique = set(hantei_list)
appeared = dict()

counter = 0
for i in hantei_list:
  if not i in appeared:
    appeared[i] = 1
  else:
    counter += appeared[i]
    appeared[i] += 1
print(counter)
### BUGGY CODE ###

from math import ceil, log2
class SegTree:
    ide_ele = 0
    def __init__(self, init_val):
        n = len(init_val)
        self.num = 2**ceil(log2(n))
        self.seg = [self.ide_ele] * (2 * self.num - 1)

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

    #####segfunc######
    def segfunc(self, x, y):
        return max(x, y)

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, a, b, k, l, r):
        """
        最初はquery(a, b, 0, 0, self.num)で呼び出す
        [a:b) でクエリをよびだす
        @see https://www.slideshare.net/iwiwi/ss-3578491
        :param a:
        :param b:
        :param k: ノード
        :param l:
        :param r:
        :return:
        """
        if r <= a or b <= l:
            return self.ide_ele
        if a <= l and r <= b:
            return self.seg[k]
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return self.segfunc(vl, vr)


n, k = map(int, input().split())
a = [int(input()) for _ in range(n)]
MAX_A = max(a)
st = SegTree([0]*MAX_A)

for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, MAX_A)
    s = st.query(min_a, max_a+1, 0, 0, st.num)
    st.update(i, max(s, 0)+1)
res = [st.query(i, i+1, 0, 0, st.num) for i in a]
print(max(res))


### FIXED CODE ###

from math import ceil, log2
import sys
z=sys.stdin.readline


# SegTreeの関数
def segfunc(x, y):
    return max(x, y)


# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = -1


# セグメント木
class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセットする
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n, k = map(int, z().split())
a = [int(z()) for _ in range(n)]
M=300001
st = SegTree([0]*M, max, 0)
res = 0
for i in a:
    min_a = max(i-k, 0)
    max_a = min(i+k, M)
    s = st.query(min_a, max_a+1)
    st.update(i, max(s, 0)+1)
    res = max(res, max(s, 0) + 1)

print(res)
### BUGGY CODE ###

from scipy.sparse import*
m=csr_matrix
n,_,p,*t=map(int,open(0).read().split())
s=[n+1]*2
r,c,d=t[::3],t[1::3],[p-c for c in t[2::3]]
u=set(csgraph.depth_first_order(m((d,(r,c)),s),1,1,0))
v=set(csgraph.depth_first_order(m((d,(c,r)),s),n,1,0))
u&=v
E=[(r,c,d)for r,c,d in zip(r,c,d)if r in u and c in u]
D=[10**9]*(n+1)
D[1]=0
for _ in'_'*n:
	for a,b,c in E:D[b]=min(D[b],D[a]+c)
ans=D[n]
for a,b,c in E:
	if D[b]>D[a]+c:
		print(-1)
		exit()
print(max(-ans,0))

### FIXED CODE ###

(N,M,P),*E=[list(map(int,s.split()))for s in open(0).readlines()]
D=[0]*2+[-9e9]*N
def f():
    for _ in D:
        for (a,b,c)in E:D[b]=max(D[b],D[a]+c-P)
    return D[N]
s=f()
print([max(s,0),-1][s<f()])
### BUGGY CODE ###

N = int(input())
def make_divisors(n):
    p = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            p+=1
            if i != n // i:
                p+=1
        i += 1
    return p
ans=0
for i in range(1,N):
    ans+=make_divisors(i)

print(ans)

### FIXED CODE ###

N = int(input())
ans=0
for i in range(1,10**6+1):
    for j in range(1,1000001):
        if i*j>N-1:
            break
        else:
            ans+=1
print(ans)
### BUGGY CODE ###

import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
dp = np.full(H+1, np.inf)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        if i < A[j]:
            dp[i] = min(dp[i], B[j])
        else:
            dp[i] = min(dp[i], dp[i-A[j]] + B[j])
            
print(int(dp[H]))

### FIXED CODE ###

import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
dp = np.full(H+1, np.inf)

dp[0] = 0
for i in range(1,H+1):
    dp[i] = np.amin( dp[np.maximum(i-A,0)] + B )

print(int(dp[H]))
### BUGGY CODE ###


n = int(input())
a = [input() for _ in range(n)]
sep=''
b = [sep.join(sorted(a[i])) for i in range(n)]
dic = {letters: b.count(letters) for letters in set(b)}

ans=0
for i in dic.values():
  ans+=i*(i-1)//2
print(ans)

### FIXED CODE ###

#python3
n = int(input())
s = [str(input()) for _ in range(n)]
sep = ''
dic = dict()
for string in s:
  tmp = sep.join(sorted(string))
  if tmp in dic:
    dic[tmp] += 1 
  else :
    dic[tmp] = 1
ans = 0
for i in dic.values(): 
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

LAMP = [[0]*w for _ in range(h)]

for i in range(1, h-1):
    for j in range(1, w-1):
        if MAZE[i][j] == '#':
            continue
        L[i][j+1] = L[i][j]+1

for i in range(1, h-1):
    for j in reversed(range(1, w-1)):
        if MAZE[i][j] == '#':
            continue
        R[i][j-1] = R[i][j]+1

for j in range(1, w-1):
    for i in range(1, h-1):
        if MAZE[i][j] == '#':
            continue
        U[i+1][j] = U[i][j]+1

for j in range(1, w-1):
    for i in reversed(range(1, h-1)):
        if MAZE[i][j] == '#':
            continue
        D[i-1][j] = D[i][j]+1

ans = 0
for i in range(1, h-1):
    for j in range(1, w-1):
        if MAZE[i][j] == '#':
            continue
        LAMP[i][j] = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
        ans = max(ans, LAMP[i][j])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(lambda x: int(x)+2, input().split())
MAZE = ['#'*w]
for _ in range(h-2):
    MAZE.append('#'+input()+'#')
else:
    MAZE.append('#'*w)

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

LAMP = [[0]*w for _ in range(h)]

for i in range(1, h-1):
    for j in range(1, w-1):
        if MAZE[i][j] == '.':
            L[i][j+1] = L[i][j]+1
        if MAZE[i][w-j] == '.':
            R[i][w-j-1] = R[i][w-j]+1

for j in range(1, w-1):
    for i in range(1, h-1):
        if MAZE[i][j] == '.':
            U[i+1][j] = U[i][j]+1
        if MAZE[h-i][j] == '.':
            D[h-i-1][j] = D[h-i][j]+1

ans = 0
for i in range(1, h-1):
    for j in range(1, w-1):
        if MAZE[i][j] == '#':
            continue
        LAMP[i][j] = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
        ans = max(ans, LAMP[i][j])

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

def m():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    cnt = 0
    for a in A:
        for b in B:
            for c in C:
                if a < b and b < c:
                    cnt +=1
    return cnt


print(m())

### FIXED CODE ###

def someone_ans():
    def binary_search(L, key, mode):
        low, high = 0, len(L)
        mid = len(L) // 2
        while low <= high - 1:
            if L[mid] < key and mode == 0 or L[mid] <= key and mode == 1:
                low = mid + 1
            else:
                high = mid
            mid = (low + high) // 2
        return high

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort()
    C.sort()
    ans = 0
    for i in B:
        Ai = binary_search(A, i, 0)
        Ci = len(C) - binary_search(C, i, 1)
        ans += Ai*Ci
    return ans


# print(m())
print(someone_ans())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
# 整数の入力
n = int(input())
# 文字列の入力
s = input()
# 数え上げ
count = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
                count +=1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
count = s.count("R")*s.count("G")*s.count("B")
for i in range(n-2):
    for j in range(i+1, (i+n+1)//2):
        if s[j] != s[i] and s[j] != s[2*j-i] and s[i] != s[2*j-i]:
            count -= 1
        # print(i, j, 2*j-i, count)
print(count)
### BUGGY CODE ###

def dp(i):
  for a,b in AB:
    C[i]=min(C[i],C[i-a if i>a else 0]+b)

H,N=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
C=[0]+[10**8]*H

for i in range(1,H+1):
  dp(i)

print(C[H])


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

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

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*n
for i in range(n):
    min_h = 10**9
    if i == 0:
        continue
    for j in range(min(i, k)):
        if dp[i-j-1] + abs(h[i-j-1] - h[i]) < min_h:
            min_h = dp[i-j-1] + abs(h[i-j-1] - h[i])
    dp[i] = min_h
        
print(dp[-1])

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [10**9]*(n+k+2)
h = np.array(h)
h = np.insert(h, len(h), np.zeros(k+2))
dp = np.array(dp)
dp[0] = 0

for i in range(n):
    dp[i+1 : i+k+1] = np.minimum(dp[i+1:i+k+1], dp[i] + np.abs(h[i+1:i+k+1] - h[i]))

print(dp[n-1])
### BUGGY CODE ###

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

def f(i, _w, _v):
    # 終了条件
    if i == N:
        return _v
    w, v = w_v[i]
    # i番目のものは入らないとき
    if _w + w > W:
        return f(i+1, _w, _v)

    # まだ入るときは両方試す
    else:
        return max(f(i+1, _w, _v), f(i+1, _w+w, _v+v))

print(f(0, 0, 0))


### FIXED CODE ###

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


# 1~i-1番目の品物から重さの総和がj以下になるように選んだときの価値
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    w, v = w_v[i]
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j-w]+v, dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

print(max(dp[N]))
### BUGGY CODE ###

h,w=map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
b=[]
for i in range(h):
    b.append(list(map(int,input().split())))
dp=[[set([]) for i in range(w)] for j in range(h)]
dp[0][0].add(a[0][0]-b[0][0])
dp[0][0].add(b[0][0]-a[0][0])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        if i==0:
            for k in dp[i][j-1]:
                dp[i][j].add(k+a[i][j]-b[i][j])
                dp[i][j].add(k+b[i][j]-a[i][j])
        elif j==0:
            for k in dp[i-1][j]:
                dp[i][j].add(k+a[i][j]-b[i][j])
                dp[i][j].add(k+b[i][j]-a[i][j])
        else:
            for k in (dp[i][j-1]|dp[i-1][j]):
                dp[i][j].add(k+a[i][j]-b[i][j])
                dp[i][j].add(k+b[i][j]-a[i][j])             
#dp[h-1][w-1]
ans=10**10
for i in dp[h-1][w-1]:
    ans=min(ans,abs(i))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
a = [[] for _ in range(H)]
for i in range(H):
    a[i] = list(map(int, input().split()))
b = [[] for _ in range(H)]
for i in range(H):
    b[i] = list(map(int, input().split()))

for i in range(H):
    for j in range(W):
        a[i][j] =abs(a[i][j]-b[i][j])

dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0].add(a[0][0])
for i in range(1,H):
    t = a[i][0]
    tmp = set()
    for k in dp[i-1][0]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[i][0] = tmp
for j in range(1,W):
    t = a[0][j]
    tmp = set()
    for k in dp[0][j-1]:
        tmp.add(k+t)
        tmp.add(abs(k-t))
    dp[0][j] = tmp
for i in range(1,H):
    for j in range(1,W):
        t = a[i][j]
        tmp = set()
        for k in (dp[i-1][j] | dp[i][j-1]):
            tmp.add(k+t)
            tmp.add(abs(k-t))
        dp[i][j] = tmp
        dp[i-1][j-1] = set()

ls = list(dp[H-1][W-1])
print(min(ls))
### BUGGY CODE ###

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

### FIXED CODE ###

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